Piotr Micek

activity

20072023

most citedPlanar graphs have bounded queue-number

73 citations · 427 across the 49 of their papers we have counts for

collaborators

Showing 2019 · math.COShow all

4 papers · 2 filters

math.CO2019

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 $m, k$ , there is no semi-online algorithm that can $k$ -co…

math.CO2019

Planar cubic graphs of small diameter

Kolja Knauer, Piotr Micek

Cubic planar $n$ -vertex graphs with faces of length at most $6$ , e.g., fullerene graphs, have diameter in $Ω (n)$ . It has been suspected, that a similar result can be shown f…

math.CO2019★ 26 cited

Improved bounds for centered colorings

Michał Dębski, Stefan Felsner, Piotr Micek +1

A vertex coloring $ϕ$ of a graph $G$ is $p$ -centered if for every connected subgraph $H$ of $G$ either $ϕ$ uses more than $p$ colors on $H$ or there is a color that appears exactly…

math.CO2019★ 1 cited

Dimension is polynomial in height for posets with planar cover graphs

Jakub Kozik, Piotr Micek, William T. Trotter

We show that height $h$ posets that have planar cover graphs have dimension $O (h^{6})$ . Previously, the best upper bound was $2^{O (h^{3})}$ . Planarity plays a key r…