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

Showing 2026Show all

15 papers · 1 filter

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…