Conjecture on cyclically 4-edge-connected cubic graphs attaining cycle covering ratio 7/5

About 1 year old · traced to

Let GG be a cubic graph. Its cycle covering ratio is the minimum length of a cycle cover divided by ∣E(G)∣|E(G)|. A cubic graph is cyclically 44-edge-connected if no edge cut of size less than 44 separates two subgraphs each containing a cycle.

Cyclic 4-edge-connectivity conjecture. Up to isomorphism, the Petersen graph is the only cyclically 44-edge-connected cubic graph with cycle covering ratio 7/57/5.

The conjecture is motivated by known infinite families attaining the ratio 7/57/5, all with cyclic connectivity 22 or 33. Its status is open.

References

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).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.