3 papers
cs.DM2019
Avoidable paths in graphs
Marthe Bonamy, Oscar Defrain, Meike Hatzel +1
We prove a recent conjecture of Beisegel et al. that for every positive integer k, every graph containing an induced P_k also contains an avoidable P_k. Avoidability generalises th…
math.CO2019
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…
math.CO2018
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…