From the 1 of 16 linked papers with an AI index.
16 papers
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
The paper proves that for any tree T and any vertex set S in a graph G, either G contains k vertex‑disjoint T‑minors rooted in S or there is a vertex set of size O(k) whose removal…
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…
Faithful universal graphs for minor-closed classes
Paul Bastide, Louis Esperet, Carla Groenland +3
It was proved by Huynh, Mohar, Šámal, Thomassen and Wood in 2021 that any countable graph containing every countable planar graph as a subgraph has an infinite clique minor. We p…
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…