16 papers
Navigating Posets with Few Maps
Stefan Felsner, JÄdrzej Hodor, Giacomo Ortali +1
We study two new parameters for finite posets motivated by the problem of efficiently determining the set of successors of a given element. A plane map of a poset is a…
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…
The grid-minor theorem revisited
Vida DujmoviÄ, Robert Hickingbotham, JÄdrzej Hodor +6
We prove that for every planar graph of treedepth , there exists a positive integer such that for every -minor-free graph , there exists a graph of treewidth a…
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…
Centered colorings and weak coloring numbers in minor-closed graph classes
JÄdrzej Hodor, Hoang La, Piotr Micek +1
Let be a proper minor-closed class of graphs. Given the minors excluded in , we determine the maximum -centered chromatic number and the maximum th…
Cops and robber in graphs with bounded vertex cover number
Prosenjit Bose, Louis Esperet, JÄdrzej Hodor +3
Meyniel's conjecture states that -vertex connected graphs have cop number . The current best known upper bound is , proved independentl…