73 citations · 427 across the 49 of their papers we have counts for
5 papers · 1 filter
Colouring bottomless rectangles and arborescences
Jean Cardinal, Kolja Knauer, Piotr Micek +3
We study problems related to colouring bottomless rectangles. One of our main results shows that for any positive integers , there is no semi-online algorithm that can -co…
Planar cubic graphs of small diameter
Kolja Knauer, Piotr Micek
Cubic planar -vertex graphs with faces of length at most , e.g., fullerene graphs, have diameter in . It has been suspected, that a similar result can be shown f…
Improved bounds for centered colorings
Michał Dębski, Stefan Felsner, Piotr Micek +1
A vertex coloring of a graph is -centered if for every connected subgraph of either uses more than colors on or there is a color that appears exactly…
Dimension is polynomial in height for posets with planar cover graphs
Jakub Kozik, Piotr Micek, William T. Trotter
We show that height posets that have planar cover graphs have dimension . Previously, the best upper bound was . Planarity plays a key r…
Planar graphs have bounded queue-number
Vida Dujmović, Gwenaël Joret, Piotr Micek +3
We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath, Leighton and Rosenberg from 1992. The key to the proof is a new structural tool called lay…