A Note on Alon–Tarsi Shortest Cycle Cover Conjecture
Journal of Graph Theory · 2026-06 · 112 (2) · 172-177
DOI: 10.1002/jgt.70026 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 20.03.2026. Verfasst von Yilun Luo und 3 weiteren Autor:innen. Die Arbeit nennt 24 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Simons Foundation.
Abstract (Originalsprache)
The shortest cycle cover conjecture (SCC conjecture), proposed by Alon and Tarsi, asserts that every bridgeless cubic graph has a cycle cover with a total length at most . Tarsi further proposed a related conjecture, the conjecture, which states that every bridgeless cubic graph has a 3‐cycle cover with a total length at most . In this paper, we prove that every cyclically odd‐‐edge‐connected cubic graph has a 3‐cycle cover with a total length at most . Consequently, the SCC conjecture and the conjecture are verified in this paper for cubic graphs with cyclic odd‐edge‐connectivity at least 29 and 17, respectively. Additionally, for cubic graphs that satisfies Kaiser–Raspaud conjecture (i.e., every bridgeless cubic graph has two perfect matchings and and a parity subgraph , such that ), the SCC conjecture and the conjecture are verified for graphs with girth at least 20 and 10, respectively.
Förderung
- National Natural Science Foundation of China
- Simons Foundation
Zitieren
APA
Luo, Y., Hao, R., Luo, R., & Zhang, C. (2026). A Note on Alon–Tarsi Shortest Cycle Cover Conjecture. Journal of Graph Theory, 112(2), 172-177. https://doi.org/10.1002/jgt.70026
Vancouver
Luo Y, Hao R, Luo R, Zhang C. A Note on Alon–Tarsi Shortest Cycle Cover Conjecture. Journal of Graph Theory. 2026;112(2):172-177. doi:10.1002/jgt.70026
BibTeX
@article{Luo2026,
author = {Luo, Yilun and Hao, Rong‐Xia and Luo, Rong and Zhang, Cun‐Quan},
title = {A Note on Alon–Tarsi Shortest Cycle Cover Conjecture},
journal = {Journal of Graph Theory},
year = {2026},
volume = {112},
number = {2},
pages = {172--177},
doi = {10.1002/jgt.70026}
}
EUVIMED