8 citations · 25 across the 33 of their papers we have counts for
28 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…
Unavoidable butterfly minors in digraphs of large cycle rank
Meike Hatzel, O-joung Kwon, Myounghwan Lee +1
Cycle rank is one of the depth parameters for digraphs introduced by Eggan in 1963. We show that there exists a function such that every digraph of cyc…
The Erdős-Pósa property for circle graphs as vertex-minors
Rutger Campbell, J. Pascal Gollin, Meike Hatzel +4
We prove that for any circle graph with at least one edge and for any positive integer , there exists an integer so that every graph either has a vertex-minor…
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…
Girth in -representable matroids
James Davies, Meike Hatzel, Kolja Knauer +2
We prove a conjecture of Geelen, Gerards, and Whittle that for any finite field and any integer , every cosimple -representable matroid with sufficiently large gi…
On graphs with a simple structure of maximal cliques
J. Pascal Gollin, Meike Hatzel, Sebastian Wiederrecht
We say that a hereditary graph class is \emph{clique-sparse} if there is a constant such that for every graph , every vertex of $G…
Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs
James Davies, Agelos Georgakopoulos, Meike Hatzel +1
In this paper, we consider the class of sphere intersection graphs in for . We show that for each integer , the class of all graphs in $…
Directed treewidth is closed under taking butterfly minors
Gunwoo Kim, Meike Hatzel, Stephan Kreutzer
Butterfly minors are a generalisation of the minor containment relation for undirected graphs to directed graphs. Many results in directed structural graph theory use this notion a…
Quasi-isometries between graphs with variable edge lengths
James Davies, Meike Hatzel, Robert Hickingbotham
This paper investigates quasi-isometries between graphs with variable edge lengths. A quasi-isometry is a mapping between metric spaces that approximately preserves distances, allo…
On graphs coverable by chubby shortest paths
Meike Hatzel, Michał Pilipczuk
Dumas, Foucaud, Perez, and Todinca [SIAM J. Disc. Math., 2024] proved that if the vertex set of a graph can be covered by shortest paths, then the pathwidth of is bound…
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…
Generating strongly 2-connected digraphs
Meike Hatzel, Stephan Kreutzer, Evangelos Protopapas +3
We prove that there exist four operations such that given any two strongly -connected digraphs and where is a butterfly-minor of , there exists a sequence $D_0,\d…
Counterexample to Babai's lonely colour conjecture
James Davies, Meike Hatzel, Liana Yepremyan
Motivated by colouring minimal Cayley graphs, in 1978, Babai conjectured that no-lonely-colour graphs have bounded chromatic number. We disprove this in a strong sense by construct…
Erdős-Pósa property of tripods in directed graphs
Marcin Briański, Meike Hatzel, Karolina Okrasa +1
Let be a directed graphs with distinguished sets of sources and sinks . A tripod in is a subgraph consisting of the union of two --…
Half-integral Erdős-Pósa property for non-null - paths
Vera Chekan, Colin Geniet, Meike Hatzel +4
For a group , a -labelled graph is an undirected graph where every orientation of an edge is assigned an element of so that opposite orientations of the same edge are…
Computing -DAGs and Parity Games
Meike Hatzel, Johannes Schröder
Treewidth on undirected graphs is known to have many algorithmic applications. When considering directed width-measures there are much less results on their deployment for algorith…
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…
Decomposition of (infinite) digraphs along directed 1-separations
Nathan Bowler, Florian Gut, Meike Hatzel +3
We introduce torsoids, a canonical structure in matching covered graphs, corresponding to the bricks and braces of the graph. This allows a more fine-grained understanding of the s…
On tree decompositions whose trees are minors
Pablo Blanco, Linda Cook, Meike Hatzel +3
In 2019, Dvořák asked whether every connected graph has a tree decomposition so that is a subgraph of and the width of is bounded…
Tight bound on treedepth in terms of pathwidth and longest path
Meike Hatzel, Gwenaël Joret, Piotr Micek +3
We show that every graph with pathwidth strictly less than that contains no path on vertices as a subgraph has treedepth at most . The bound is best possible up to…
Graphs with at most two moplexes
Clément Dallard, Robert Ganian, Meike Hatzel +2
A moplex is a natural graph structure that arises when lifting Dirac's classical theorem from chordal graphs to general graphs. While every non-complete graph has at least two mopl…
Tuza's Conjecture for Threshold Graphs
Marthe Bonamy, Łukasz Bożyk, Andrzej Grzesik +4
Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds…