19 papers · 1 filter
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…
Odd coloring graphs with linear neighborhood complexity
James Davies, Meike Hatzel, Kolja Knauer +2
We prove that any class of graphs with linear neighborhood complexity has bounded improper odd chromatic number. As a result, if is the class of all circle graphs, or…
Unavoidable induced subgraphs in graphs with complete bipartite induced minors
Maria Chudnovsky, Meike Hatzel, Tuukka Korhonen +2
We prove that if a graph contains the complete bipartite graph as an induced minor, then it contains a cycle of length at most~12 or a theta as an induced subgraph. W…