Cycle decompositions of pathwidth-6 graphs
- Hajós' conjecture asserts that a simple Eulerian graph on n vertices can be decomposed into at most [(n-1)/2] 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.
Author: | Elke Fuchs, Laura GellertORCiD, Irene HeinrichORCiD |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-79526 |
DOI: | https://doi.org/10.1002/jgt.22516 |
ISSN: | 1097-0118 |
Parent Title (English): | Journal of Graph Theory |
Publisher: | Wiley |
Document Type: | Article |
Language of publication: | English |
Date of Publication (online): | 2024/04/04 |
Year of first Publication: | 2019 |
Publishing Institution: | Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau |
Date of the Publication (Server): | 2024/04/04 |
Issue: | 94/2 |
Page Number: | 28 |
First Page: | 224 |
Last Page: | 251 |
Source: | https://onlinelibrary.wiley.com/doi/10.1002/jgt.22516 |
Faculties / Organisational entities: | Kaiserslautern - Fachbereich Mathematik |
DDC-Cassification: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
Collections: | Open-Access-Publikationsfonds |
Licence (German): | Zweitveröffentlichung |