Piotr Micek
I am an associate professor at
Jagiellonian University
Faculty of Mathematics and Computer Science
Theoretical Computer Science Department
reach me:
firstname.lastname@gmail.com
+48126647594
find me:
room 3151, Faculty of Math and Computer Science
This is my Berlin's website. I spent some years in Berlin and this website became the main place where I collect my stuff.
From September 2016 till February 2017,
I was a BMS Substitute Professor at
Freie Universität Berlin within
Tibor Szabó's
Combinatorics and Graph Theory Group.
For almost two years I was a
Mobility Plus
research fellow at
Technische Universität Berlin within
Stefan Felsner's
Diskrete Mathematik Group.
Upcoming
Papers
As of Sep 10, 2017. Conference and journal versions merged.
Here is my Google Scholar profile.

Nowhere dense graph classes and dimension
with
Gwenaël Joret,
Patrice Ossona de Mendez, and
Veit Wiechert
submitted

Separating treechromatic number from pathchromatic number
with
Fidel BarreraCruz,
Stefan Felsner,
Tamás Mészáros,
Heather Smith,
Libby Taylor, and
William T. Trotter
submitted

Boolean dimension and treewidth
with
Stefan Felsner and
Tamás Mészáros
manuscript

Boolean dimension, components and blocks
with
Tamás Mészáros and
William T. Trotter
submitted

Seymour's conjecture on 2connected graphs of large pathwidth
with
Tony Huynh,
Gwenaël Joret, and
David Wood
manuscript

Variants of online chain partition problem of posets
with
Bartłomiej Bosek
Proceedings of Computational Logic and Applications, CLA 2004,
Electronic Notes on Theoretical Computer Science: 140, 3–13, 2005

Online coloring of Isfree graphs and coplanar graphs
with
Iwona Cieślik and
Marcin Kozik
Proceedings of Computational logic and applications, CLA 2005,
Discrete Mathematics & Theoretical Computer Science Proceedings, AF., 61–68, 2006

Online adaptive chain covering of upgrowing posets
with
Bartłomiej Bosek
Proceedings of Computational Logic and Applications, CLA 2005,
Discrete Mathematics & Theoretical Computer Science Proceedings, AF., 37–48, 2006

Online chain partitioning of upgrowing interval orders
with
Patrick Baier and
Bartłomiej Bosek
Order (ORDE): 24.1, pp. 1–13, 2007

A graphgrabbing game
with
Bartosz Walczak
Combinatorics, Probability & Computing (CPC): 20.4, 623–629, 2011

How to eat 4/9 of a pizza
with
Kolja Knauer, and
Torsten Ueckerdt
Discrete Mathematics (DM): 311.16, 1635–1645, 2011

Parity in graph sharing games
with
Bartosz Walczak
Discrete Mathematics (DM): 312.10, 1788–1795, 2012

Online version of Rabinovitch theorem for proper intervals
with
Bartłomiej Bosek,
Kamil Kloch, and
Tomasz Krawczyk
Discrete Mathematics (DM): 312.23, 3426–3436, 2012

Online chain partitions of orders: a survey
with
Bartłomiej Bosek,
Stefan Felsner,
Kamil Kloch,
Tomasz Krawczyk, and
Grzegorz Matecki
Order (ORDE): 29.1, 4973, 2012

Online chain partitions of upgrowing semiorders
with
Stefan Felsner,
Kamil Kloch, and
Grzegorz Matecki
Order (ORDE): 30.1,85–101, 2013

Making triangles colorful
with
Jean Cardinal,
Kolja Knauer, and
Torsten Ueckerdt
Journal of Computational Geometry: 4.1, 240–246, 2013

Online dimension of semiorders
with
Bartłomiej Bosek,
Kamil Kloch, and
Tomasz Krawczyk
Order (ORDE): 30.2, 593–615, 2013

Coloring hypergraphs induced by dynamic point sets and bottomless rectangles
with
Andrei Asinowski,
Jean Cardinal,
Nathann Cohen,
Sébastien Collette,
Thomas Hackl,
Michael Hoffmann,
Kolja Knauer,
Stefan Langerman,
Michał Lasoń,
Günter Rote, and
Torsten Ueckerdt
Proc. Workshop on Algorithms and Data Structures (WADS), Algorithms and data structures, Lecture Notes in Computer Science: 8037, 7384, 2013

Trianglefree geometric intersection graphs with large chromatic number
with Arkadiusz Pawlik,
Jakub Kozik,
Tomasz Krawczyk,
Michał Lasoń,
William T. Trotter, and
Bartosz Walczak
Discrete & Computational Geometry (DCG): 50 , 714726, 2013

Nonrepetitive choice number of trees
with Jakub Kozik
SIAM Journal on Discrete Mathematics (SIDMA): 27, no. 1, 436446, 2013

A new approach to nonrepetitive sequences
with Jarosław Grytczuk and
Jakub Kozik
Random Structures and Algorithms (RSA): 42, Issue 2, 214225, 2013

Coloring intersection graphs of arcconnected sets in the plane
with Michał Lasoń,
Arkadiusz Pawlik, and
Bartosz Walczak
final version:
Discrete & Computational Geometry (DCG): 52, Issue 2, 399415, 2014
preliminary version:
7th European Conference on Combinatorics, Graph Theory and Applications (EuroComb'13): vol. 16 of CRM Series, 299304, 2013

Towards an online version of Ohba’s conjecture
with Jakub Kozik, and
Xuding Zhu
European Journal of Combinatorics (EJC): 36, 110121, 2014

Outerplanar graph drawings with few slopes
with Kolja Knauer,
Bartosz Walczak
final version: Computational Geometry: Theory and Applications (CGTA): 47 (5), 614624, 2014
preliminary version: Computing and combinatorics. Lecture Notes in Comput. Sci.: vol. 7434, 2012

Lower bounds for online graph colorings
with
Grzegorz Gutowski,
Jakub Kozik
and
Xuding Zhu
Algorithms and Computation: 25th International Symposium (ISAAC) Proceedings: 507515, 2014

An online competitive algorithm for coloring bipartite graphs without long induced paths
with
Veit Wiechert
full version: Algorithmica (ALGO) 77, 10601070, 2017.
preliminary version: An online competitive algorithm for coloring P8free bipartite graphs,
Algorithms and Computation: 25th International Symposium (ISAAC) Proceedings: 516527, 2014

An extremal problem on crossing vectors
with Michał Lasoń,
Noah Streib,
William T. Trotter, and
Bartosz Walczak
Journal of Combinatorial Theory Series A (JCTA): 128, 41–55, 2014

Trianglefree intersection graphs of line segments with large chromatic number
with
Arkadiusz Pawlik,
Jakub Kozik,
Tomasz Krawczyk,
Michał Lasoń,
William T. Trotter, and
Bartosz Walczak
Journal of Combinatorial Theory Series B (JCTB), 105: 610, 2014.

Making octants colorful, and related covering decomposition problems
with
Jean Cardinal,
Kolja Knauer, and
Torsten Ueckerdt
full version: SIAM Journal on Discrete Mathematics (SIDMA) 28 (4): 19481959, 2014
preliminary version: Proceedings of the 25th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'14): 14241432, 2014

Online coloring between two lines
with
Stefan Felsner
and
Torsten Ueckerdt
31st International Symposium on Computational Geometry (SoCG),
LIPIcs 34: 630641, 2015

A note on concurrent graph sharing games
with
Steven Chaplick,
Torsten Ueckerdt, and
Veit Wiechert
Integers 16, No. G1, 2016.

Pathwidth and nonrepetitive list colorings
with Adam Gągol,
Gwenaël Joret, and
Jakub Kozik
Electronic Journal of Combinatorics (EJC) Vol. 23, Issue 4, 2016.

Treewidth and dimension
with
Gwenaël Joret,
Kevin G. Milans,
William T. Trotter,
Bartosz Walczak, and
Ruidong Wang
Combinatorica, 36/4:431450, 2016.

On the dimension of posets with cover graphs of treewidth 2
with
Gwenaël Joret,
William T. Trotter,
Ruidong Wang, and
Veit Wiechert
Order (ORDE) 34.2:185234, 2017

Graph sharing game and the structure of weighted graphs with a forbidden subdivision
with Adam Gągol and
Bartosz Walczak
Journal of Graph Theory (JGT) 85.1:2250, 2017

Topological minors of cover graphs and dimension
with
Veit Wiechert
Journal of Graph Theory (JGT) 86.3:295–314, 2017

Sparsity and dimension
with
Gwenaël Joret
and
Veit Wiechert
full version: Combinatorica 2017.
preliminary version: Proceedings of the 27th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'16): 18041813, 2016.

Burling graphs, chromatic number, and orthogonal treedecompositions
with
Stefan Felsner,
Gwenaël Joret,
William T. Trotter, and
Veit Wiechert
full version: to appear in Electronic Journal of Combinatorics (EJC).
extended abstract:
Electronic Notes in Discrete Mathematics 61 (2017). The European Conference
on Combinatorics, Graph Theory and Applications (EuroComb’17):415–420.

On an extremal problem for poset dimension
with
Grzegorz Guśpiel and
Adam Polak
Order (ORDE) 2017.

Planar posets have dimension at most linear in their height
with
Gwenaël Joret and
Veit Wiechert
SIAM Journal on Discrete Mathematics (SIDMA) 31(4), 2754–2790, 2017.
other unpublished manuscripts