From the 3 of 19 linked papers with an AI index.
18 papers · 1 filter
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…
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…
ErdÅs--Pósa property of cycles that are far apart
Vida DujmoviÄ, Gwenaël Joret, Piotr Micek +1
We prove that there exist functions such that for all nonnegative integers and , for every graph , either contains cycles such that…
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…
Tree decompositions whose trees are subgraphs: An application of Simon's factorization
Romain Bourneuf, Gwenaël Joret, Piotr Micek +2
We show that every connected graph has a tree decomposition indexed by a tree such that is a subgraph of and the width of the tree decomposition is bounded from abo…
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…