4 papers · 1 filter
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…
Optimal Bounds for the k-Disjoint Paths Problem
Dario Cavallaro, Maximilian Gorsky, Stephan Kreutzer +2
The Graph Minors Series of Robertson and Seymour forms the foundation of algorithmic structural graph theory, yielding fixed-parameter algorithms for problems such as Disjoint Path…
Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width
Dario Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer
We prove that every class of Eulerian directed graphs of bounded carving width (equivalently of bounded degree and treewidth) is well-quasi-ordered by strong immersion. In fact, we…
Cycles of Well-Linked Sets II: an Elementary Bound for the Directed Grid Theorem
Meike Hatzel, Stephan Kreutzer, Marcelo Garlet Milani +1
In 2015, Kawarabayashi and Kreutzer proved the Directed Grid Theorem - the generalisation of the well-known Excluded Grid Theorem to directed graphs - confirming a conjecture by Re…