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

From papers

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.

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

No solutions have been posted yet.