17 papers
Minimal Cayley graphs with large chromatic number
James Davies, Meike Hatzel, Liana Yepremyan
Resolving Babai's minimal Cayley graph problem, we construct finite minimal Cayley graphs with arbitrarily large chromatic number.
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…
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…
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…
Cycles of Well-Linked Sets I: an Elementary Bound for Directed Cycle Packing
Meike Hatzel, Stephan Kreutzer, Marcelo Garlet Milani +1
In 1996, Reed, Robertson, Seymour and Thomas [Combinatorica 1996] proved Younger's Conjecture, which states that, for all directed graphs , there exists a function such that…
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…