P. Micek

activity

20242026

most citedTight bound for the Erdős-Pósa property of tree minors

1 citations · 1 across the 20 of their papers we have counts for

collaborators

24 papers

math.CO2026

Asymptotic dimension of graphs excluding an induced or fat minor

Robert Hickingbotham, Freddie Illingworth, Piotr Micek +1

Asymptotic dimension is a large-scale invariant of metric spaces that was introduced by Gromov (1993). A major open problem in coarse graph theory asks whether, for every fixed gra…

math.CO2026

Strong coloring numbers of grids

Piotr Micek, Torsten Ueckerdt

For positive integers $n$ and $d$ , the $d$ -dimensional grid of side length $n$ is the graph $G (n, d)$ with vertex set $[n]^{d}$ , in which two vertices are adjacent if they differ by $…

math.CO2026

Relative Dimension of Posets

Dominik Dürrschnabel, Jędrzej Hodor, Piotr Micek +2

Dimension of partially ordered sets (posets for short) can be seen as a measure of how much space is needed to store posets. Refining the definition of dimension, or actually the l…

math.CO2026

Superlinear separation between linear and centered colorings

Jędrzej Hodor, Piotr Micek

A vertex-coloring of a graph is centered if every connected subgraph has a vertex with a unique color. A vertex-coloring of a graph is linear if every path in the graph has a verte…

math.CO2026

Product structure of graphs excluding a topological minor

Jędrzej Hodor, Hoang La, Piotr Micek +1

We prove that, for all positive integers $h$ and $t$ and every graph $X$ with $td (X) \leq h$ , there exists a positive integer $c (X, t)$ such that every graph $G$ with $\mat…

math.CO2026

Row pathwidth of complete binary trees

Jędrzej Hodor, Piotr Micek

We show that if a complete binary tree of height $h$ is isomorphic to a subgraph of the strong product of a graph $H$ and a path, then $pw (H)$ is $Ω (h)$ . This solves a pro…

math.CO2026

Far-apart Erdős--Pósa property of long cycles

Maria Chudnovsky, Vida Dujmović, Gwenaël Joret +4

We prove that there exist functions $f : N^{2} \to N$ and $g : N \to N$ such that for all positive integers $k$ , $d$ , and $ℓ \geq 3$ , every graph $G$ either c…

math.CO2026

Planarity and dimension II

Heather S. Blake, Jędrzej Hodor, Piotr Micek +2

The dimension of a poset $P$ is the minimum positive integer $d$ such that $P$ is an induced subposet of $R^{d}$ equipped with the product order. We give a constant-factor p…

cs.DM2026

Adjacency labelling for proper minor-closed graph classes

Vida Dujmović, Cyril Gavoille, Gwenaël Joret +3

We show that every proper minor-closed class of graphs admits a $(1 + o (1)) lo g_{2} n$ -bit adjacency labelling scheme. Equivalently, for every proper minor-closed class $G$ a…

cs.DM2026

Sample compression schemes for balls in structurally sparse graphs

Romain Bourneuf, Jędrzej Hodor, Piotr Micek +1

Sample compression schemes were defined by Littlestone and Warmuth (1986) as an abstraction of the structure underlying many learning algorithms. In a sample compression scheme, we…

math.CO2026

Centered colorings and weak coloring numbers in minor-closed graph classes

Jędrzej Hodor, Hoang La, Piotr Micek +1

Let $C$ be a proper minor-closed class of graphs. Given the minors excluded in $C$ , we determine the maximum $q$ -centered chromatic number and the maximum $q$ th…

math.CO2026

Tree decompositions whose trees are subgraphs: An application of Simon's factorization

Romain Bourneuf, Gwenaël Joret, Piotr Micek +2

We show that every connected graph $G$ has a tree decomposition indexed by a tree $T$ such that $T$ is a subgraph of $G$ and the width of the tree decomposition is bounded from abo…

math.CO2026

Cops and robber in graphs with bounded vertex cover number

Prosenjit Bose, Louis Esperet, Jędrzej Hodor +3

Meyniel's conjecture states that $n$ -vertex connected graphs have cop number $O (n)$ . The current best known upper bound is $n / 2^{(1 - o (1)) l o g n}$ , proved independentl…

math.CO2026

Note on the treewidth of graphs excluding a disjoint union of cycles as a minor

Gwenaël Joret, Piotr Micek

For a planar graph $H$ , let $f (H)$ denote the minimum integer such that all graphs excluding $H$ as a minor have treewidth at most $f (H)$ . We show that if $H$ is a disjoint union o…

math.CO2026

A coarse Gallai theorem

Marc Distel, Ugo Giocanti, Jędrzej Hodor +2

We prove that there exist functions $f$ and $g$ such that for all positive integers $k$ and $d$ , for every graph $G$ and every subset $A$ of the vertices of $G$ , either $G$ contain…

math.CO2025

Planarity and dimension I

Heather Smith Blake, Jędrzej Hodor, Piotr Micek +2

The dimension of a partially ordered set $P$ (poset for short) is the least positive integer $d$ such that $P$ is isomorphic to a subposet of $R^{d}$ with the natural produc…

math.CO2025

Shallow brambles

Nicolas Bousquet, Wouter Cames van Batenburg, Louis Esperet +2

A graph class $C$ has polynomial expansion if there is a polynomial function $f$ such that for every graph $G \in C$ , each of the depth- $r$ minors of $G$ has ave…

math.CO2024

Erdős--Pósa property of cycles that are far apart

Vida Dujmović, Gwenaël Joret, Piotr Micek +1

We prove that there exist functions $f, g : N \to N$ such that for all nonnegative integers $k$ and $d$ , for every graph $G$ , either $G$ contains $k$ cycles such that…

math.CO2024

Centered colorings in minor-closed graph classes

Jędrzej Hodor, Hoang La, 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 exact…

math.CO2024

Planar graphs in blowups of fans

Marc Distel, Vida Dujmović, Gwenaël Joret +3

We show that every $n$ -vertex planar graph is contained in the graph obtained from a fan by blowing up each vertex by a complete graph of order $O (n lo g^{2} n)$ . Equivalently,…

math.CO2024

Weak coloring numbers of minor-closed graph classes

Jędrzej Hodor, Hoang La, Piotr Micek +1

We study the growth rate of weak coloring numbers of graphs excluding a fixed graph as a minor. Van den Heuvel et al. (European J. of Combinatorics, 2017) showed that for a fixed g…

math.CO2024

Vertex Ranking of Degenerate Graphs

John Iacono, Piotr Micek, Pat Morin +1

An $ℓ$ -vertex-ranking of a graph $G$ is a colouring of the vertices of $G$ with integer colours so that in any connected subgraph $H$ of $G$ with diameter at most $ℓ$ , there…

math.CO2024

Quickly excluding an apex-forest

Jędrzej Hodor, Hoang La, Piotr Micek +1

We give a short proof that for every apex-forest $X$ on at least two vertices, graphs excluding $X$ as a minor have layered pathwidth at most $2∣ V (X) ∣ - 3$ . This improves upon a resu…

math.CO2024★ 1 cited

Tight bound for the Erdős-Pósa property of tree minors

Vida Dujmović, Gwenaël Joret, Piotr Micek +1

Let $T$ be a tree on $t$ vertices. We prove that for every positive integer $k$ and every graph $G$ , either $G$ contains $k$ pairwise vertex-disjoint subgraphs each having a $T$ mi…