From the 2 of 19 linked papers with an AI index.
19 papers
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…
Product structure of graphs excluding a topological minor
Jędrzej Hodor, Hoang La, Piotr Micek +1
We prove that, for all positive integers and and every graph with , there exists a positive integer such that every graph with $\mat…
Row pathwidth of complete binary trees
Jędrzej Hodor, Piotr Micek
We show that if a complete binary tree of height is isomorphic to a subgraph of the strong product of a graph and a path, then is . This solves a pro…
Far-apart ErdÅs--Pósa property of long cycles
Maria Chudnovsky, Vida DujmoviÄ, Gwenaël Joret +4
The authors prove that for any graph, either it contains many cycles of length at least ℓ that are pairwise far apart, or a small vertex set can be removed to eliminate all such lo…
Adjacency labelling for proper minor-closed graph classes
Vida DujmoviÄ, Cyril Gavoille, Gwenaël Joret +3
The paper proves that every proper minor‑closed class of graphs admits an adjacency labeling scheme using (1+o(1))·log₂ n bits, equivalently showing the existence of an n^{1+o(1)}‑…
Planarity and dimension II
Heather S. Blake, JÄdrzej Hodor, Piotr Micek +2
The dimension of a poset is the minimum positive integer such that is an induced subposet of equipped with the product order. We give a constant-factor p…