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.
Verfasser*innenangaben: | 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 |
Titel des übergeordneten Werkes (Englisch): | Journal of Graph Theory |
Verlag: | Wiley |
Dokumentart: | Wissenschaftlicher Artikel |
Sprache der Veröffentlichung: | Englisch |
Datum der Veröffentlichung (online): | 04.04.2024 |
Jahr der Erstveröffentlichung: | 2019 |
Veröffentlichende Institution: | Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau |
Datum der Publikation (Server): | 04.04.2024 |
Ausgabe / Heft: | 94/2 |
Seitenzahl: | 28 |
Erste Seite: | 224 |
Letzte Seite: | 251 |
Quelle: | https://onlinelibrary.wiley.com/doi/10.1002/jgt.22516 |
Fachbereiche / Organisatorische Einheiten: | Kaiserslautern - Fachbereich Mathematik |
DDC-Sachgruppen: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
Sammlungen: | Open-Access-Publikationsfonds |
Lizenz (Deutsch): | Zweitveröffentlichung |