P. Micek

activity

20242026

collaborators

Showing math.COShow all

20 papers · 1 filter

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…