25 papers
A relaxation of the Bermond-Thomassen conjecture
Stéphane Bessy, Matthijs Muis, Jean-Sébastien Sereni +2
The well-known Bermond-Thomassen conjecture states that every digraph of minimum out-degree at least contains vertex-disjoint directed cycles. Despite being posed in 198…
A directed flat wall theorem excluding a crossrow grid
Meike Hatzel, Ken-ichi Kawarabayashi, Stephan Kreutzer +1
The graph minor project contains the most influential results in recent undirected graph theory research. There has been progress in recent years in generalising some of their resu…
Spanning Paths and Cycles: Structural Limitations of the Irrelevant Vertex Technique
Dimitrios M. Thilikos, Sebastian Wiederrecht
The Irrelevant Vertex Technique is one of the cornerstones of algorithmic graph theory, underlying Robertson and Seymour's algorithm for \textsc{Disjoint Paths} and much of the alg…
An ErdÅs-Pósa theorem for cycles and faces of distinct lengths
J. Pascal Gollin, Maximilian Gorsky, Meike Hatzel +6
We show that for every , every graph contains vertex-disjoint cycles of different lengths, or there exists a set with $|X| \in \mathcal…
The price of homogeneity is polynomial
Maximilian Gorsky, MichaÅ T. Seweryn, Sebastian Wiederrecht
We provide explicit and polynomial bounds for the Homogeneous Wall Lemma which occurred for the first time implicitly in the th entry of Robertson and Seymour's Graph Minors Se…
Bounds on treewidth via excluding disjoint unions of cycles
Meike Hatzel, Chun-Hung Liu, Bruce Reed +1
One of the fundamental results in graph minor theory is that for every planar graph~, there is a minimum integer~ such that graphs with no minor isomorphic to~ have tre…