Cycle decompositions of pathwidth-6 graphs |
| |
Authors: | Elke Fuchs Laura Gellert Irene Heinrich |
| |
Institution: | 1. Institut für Optimierung und Operations Research, Universität Ulm, Ulm, Germany;2. AG Algorithmen und Komplexität, Technische Universität Kaiserslautern, Kaiserslautern, Germany |
| |
Abstract: | Hajós' conjecture asserts that a simple Eulerian graph on vertices can be decomposed into at most cycles. The conjecture is only proved for graph classes in which every element contains vertices of degree 2 or 4. We develop new techniques to construct cycle decompositions. They work on the common neighborhood of two degree-6 vertices. With these techniques, we find structures that cannot occur in a minimal counterexample to Hajós' conjecture and verify the conjecture for Eulerian graphs of pathwidth at most 6. This implies that these graphs satisfy the small cycle double cover conjecture. |
| |
Keywords: | circuit cycle decomposition decomposition Eulerian graphs Hajós conjecture |
|
|