Conjecture on cyclically 4-edge-connected cubic graphs attaining cycle covering ratio 7/5
Conjecture on cyclically 4-edge-connected cubic graphs attaining cycle covering ratio 7/5
Let be a cubic graph. Its cycle covering ratio is the minimum length of a cycle cover divided by . A cubic graph is cyclically -edge-connected if no edge cut of size less than separates two subgraphs each containing a cycle.
Cyclic 4-edge-connectivity conjecture. Up to isomorphism, the Petersen graph is the only cyclically -edge-connected cubic graph with cycle covering ratio .
The conjecture is motivated by known infinite families attaining the ratio , all with cyclic connectivity or . Its status is open.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Ján Karabáš, Edita Máčajová, Roman Nedela and Martin Škoviera, “Cubic graphs of colouring defect 3 and conjectures of Berge and Alon-Tarsi”, arXiv:2505.17569 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.