3 citations · 8 across the 25 of their papers we have counts for
7 papers · 1 filter
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…
Erdős-Pósa property of rooted tree minors
Quentin Claus, Gwenaël Joret, Clément Rambaud +1
Fiorini, Joret, and Wood (2013) showed that tree minors satisfy the so-called Erdős-Pósa property with a linear bound: For every tree there exists a constant such th…
On the -inversion diameter of oriented graphs
Frédéric Havet, Clément Rambaud, Caroline Silva
In an oriented graph , the {\it inversion} of a subset of vertices consists in reversing the orientation of all arcs with both endvertices in . The {\it -…
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…
Blow-up structure of graphs excluding a tree or an apex-tree as a minor
Quentin Claus, Gwenaël Joret, Clément Rambaud
We prove blow-up structure theorems for graphs excluding a tree or an apex-tree as a minor. First, we show that for every -vertex tree with and radius , and eve…
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…