8 citations · 25 across the 33 of their papers we have counts for
7 papers · 1 filter
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…