4 papers · 1 filter
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 --…
Cyclewidth and the Grid Theorem for Perfect Matching Width of Bipartite Graphs
Meike Hatzel, Roman Rabinovich, Sebastian Wiederrecht
A connected graph G is called matching covered if every edge of G is contained in a perfect matching. Perfect matching width is a width parameter for matching covered graphs based…
The Tight Cut Decomposition of Matching Covered Uniformable Hypergraphs
Isabel Beckenbach, Meike Hatzel, Sebastian Wiederrecht
The perfect matching polytope, i.e. the convex hull of (incidence vectors of) perfect matchings of a graph is used in many combinatorial algorithms. Kotzig, Lovász and Plummer deve…