Perfect matching index and cycle double covers containing 2-factors in bridgeless cubic graphs (Conjecture 5.2/6.1 of Máčajová, Mazzuoccolo, Mkrtchyan and Zerafa)

A bridgeless cubic graph $G$ has perfect matching index $\chi'_e(G)$: the minimum number of perfect matchings whose union covers $E(G)$ (also called the excessive index). Máčajová, Mazzuoccolo, Mkrtchyan and Zerafa conjectured (Conjecture 6.1 of 'Some snarks are worse than others', stated there as equivalent to their Conjecture 5.2) that $\chi'_e(G)>4$ if and only if every cycle double cover of $G$ fails to contain a 2-factor of $G$; equivalently, the shortest cycle cover length satisfies $scc(G)=\frac{4}{3}|E(G)|$ exactly when $E(G)$ can be covered by four perfect matchings. The direction for graphs with $\chi'_e(G)\le4$ is a 2015 theorem of Steffen, so the open core asks whether every graph needing five or more perfect matchings has shortest cycle cover strictly longer than $\frac{4}{3}|E(G)|$ — equivalently whether every such graph is 'frumious': adding parallel copies of any single perfect matching never makes the multigraph Class I. The conjecture is confirmed for the Petersen graph, for the Esperet–Mazzuoccolo family, for treelike snarks, and for all snarks of colouring defect 3; it remains open for the rest of the class $S_{\ge5}$, in particular the known cyclically 4-edge-connected snarks of colouring defect at least 4 constructed via tetrahedral flows.

Background

A graph is cubic if every vertex has degree three, and bridgeless if deleting no single edge disconnects it. By Vizing's theorem every cubic graph has edge-chromatic number 3 or 4; graphs with a 3-edge-colouring are called Class I and the others Class II. A snark is a bridgeless cubic graph that is not 3-edge-colourable; a nontrivial snark is one that is additionally cyclically 4-edge-connected (no set of fewer than 4 edges separates two circuits of the graph) and has girth at least 5. Snarks are the standard minimal candidates for counterexamples to several conjectures about cycles and edge colourings.

A perfect matching (1-factor) is a set of edges covering every vertex exactly once, and a 2-factor is a spanning 2-regular subgraph; in a cubic graph the complement of a perfect matching is always a 2-factor. The perfect matching index of a graph $G$, written $\chi'_e(G)$ and also known in the literature as the excessive index, is the minimum number of perfect matchings whose union covers $E(G)$. For a bridgeless cubic graph this number is 3, 4, or at least 5. The Berge–Fulkerson conjecture — Fulkerson's 1971 conjecture that every bridgeless cubic graph has six perfect matchings covering each edge exactly twice, proved equivalent by Mazzuoccolo to Berge's conjecture that five perfect matchings always suffice to cover the edges — predicts $\chi'_e(G)\le5$ for every bridgeless cubic graph. Writing $S_4$ for the bridgeless cubic graphs with $\chi'_e(G)=4$ and $S_{\ge5}$ for those with $\chi'_e(G)\ge5$, any cubic counterexample to the cycle double cover conjecture, to the Fan–Raspaud conjecture (every bridgeless cubic graph has three perfect matchings with empty common intersection), or to the shortest cycle cover conjecture of Alon and Tarsi must lie in $S_{\ge5}$; for graphs in $S_4$ all three are known. Only two of the more than sixty million nontrivial snarks of order at most 36 belong to $S_{\ge5}$, yet infinite nontrivial families in $S_{\ge5}$ were constructed by Esperet and Mazzuoccolo, by Abreu, Kaiser, Labbate and Mazzuoccolo (the treelike snarks), and by Máčajová and Škoviera. Máčajová and Škoviera's constructions rest on their theory of tetrahedral flows, which describes 4-perfect-matching covers in terms of certain flows and yields systematic constructions of snarks in $S_{\ge5}$.

A cycle cover of a graph $G$ is a family of even subgraphs whose union covers every edge at least once; $scc(G)$ denotes the minimum total length (sum of circuit lengths) of a cycle cover of $G$. A cycle double cover (CDC) is a family of cycles in which every edge lies in exactly two members; the cycle double cover conjecture asserts that every bridgeless graph has one. The 7/5-conjecture of Alon and Tarsi asserts $scc(G)\le\frac{7}{5}|E(G)|$ for every bridgeless graph. Every cycle cover of a bridgeless cubic graph has length at least $\frac{4}{3}|E(G)|$, and Steffen proved that $\chi'_e(G)\le4$ implies $scc(G)=\frac{4}{3}|E(G)|$ (and that every snark in $S_4$ admits a cycle double cover).

For a set $N\subseteq E(G)$, let $G+N$ denote the multigraph obtained by adding one parallel copy of every edge of $N$. Máčajová, Mazzuoccolo, Mkrtchyan and Zerafa studied three parameters on bridgeless cubic graphs: $l(G)$, the minimum number of perfect matchings whose addition to $G$ produces a Class I multigraph; $l_M(G)$, the minimum number of copies of one fixed perfect matching $M$ whose addition produces a Class I multigraph; and $scc(G)$. They call $G$ frumious if $l_M(G)=+\infty$ for every perfect matching $M$ of $G$. Their Theorem 5.4 states that $scc(G)>\frac{4}{3}|E(G)|$ if and only if $G$ is frumious (otherwise $scc(G)=\frac{4}{3}|E(G)|$), and they observe that $l_M(G)$ is finite exactly when the 2-factor $G-M$ is contained in some cycle double cover of $G$. On this basis they posed Conjecture 5.2 — $scc(G)=\frac{4}{3}|E(G)|$ if and only if $\chi'_e(G)\le4$ — and restated it equivalently as Conjecture 6.1, which ties the perfect matching index to which spanning subgraphs the cycle double covers of a graph can contain. A third measure of distance from 3-edge-colourability, the colouring defect of a cubic graph — the minimum number of edges left uncovered by any three perfect matchings, at least 3 for every snark — later turned out to organise the progress on this conjecture.

Problem Statement

Prove or disprove the following conjecture of Máčajová, Mazzuoccolo, Mkrtchyan and Zerafa ('Some snarks are worse than others', Conjecture 6.1, stated there as equivalent to their Conjecture 5.2): for every bridgeless cubic graph $G$, $\chi'_e(G)>4$ if and only if every cycle double cover of $G$ fails to contain a 2-factor of $G$. Equivalently: $scc(G)=\frac{4}{3}|E(G)|$ if and only if $\chi'_e(G)\le4$.

The implication from $\chi'_e(G)\le4$ (a shortest cycle cover of length exactly $\frac{4}{3}|E(G)|$, and the existence of a cycle double cover containing a 2-factor) is a theorem of Steffen, so the open content is the converse direction which, by Theorem 5.4 of the source paper, is equivalent to each of the following statements about every bridgeless cubic graph $G$ with $\chi'_e(G)\ge5$ (that is, every graph in $S_{\ge5}$): (i) $scc(G)>\frac{4}{3}|E(G)|$; (ii) $G$ is frumious, i.e. $l_M(G)=+\infty$ for every perfect matching $M$ of $G$, or equivalently $G+tM$ is Class II for every positive integer $t$ and every perfect matching $M$ of $G$; (iii) no cycle double cover of $G$ contains any 2-factor of $G$.

The conjecture is confirmed for the Petersen graph (the smallest snark, on 10 vertices), for the family of Esperet and Mazzuoccolo, for the treelike snarks of Abreu, Kaiser, Labbate and Mazzuoccolo, and for all snarks of colouring defect 3 (colouring defect being the minimum number of edges left uncovered by any three perfect matchings). A counterexample, if one exists, must therefore be a snark of colouring defect at least 4 with $\chi'_e\ge5$. The problem is to be answered in its full generality over all bridgeless cubic graphs (multigraphs without loops, per the source's conventions).

References

1. Edita Máčajová, Giuseppe Mazzuoccolo, Vahan Mkrtchyan, Jean Paul Zerafa, 'Some snarks are worse than others', European Journal of Combinatorics 117 (2024) 103832, DOI 10.1016/j.ejc.2023.103832; arXiv:2004.14049, https://arxiv.org/abs/2004.14049
2. Eckhard Steffen, '1-Factor and Cycle Covers of Cubic Graphs', Journal of Graph Theory 78 (2015) 195-206, DOI 10.1002/jgt.21798, https://doi.org/10.1002/jgt.21798
3. Louis Esperet, Giuseppe Mazzuoccolo, 'On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings', Journal of Graph Theory 77 (2014) 144-157, DOI 10.1002/jgt.21778; arXiv:1301.6926, https://arxiv.org/abs/1301.6926
4. Edita Máčajová, Martin Škoviera, 'Cubic graphs that cannot be covered with four perfect matchings', Journal of Combinatorial Theory, Series B 150 (2021) 144-176, DOI 10.1016/j.jctb.2021.04.004; arXiv:2008.01398, https://arxiv.org/abs/2008.01398
5. Martin Škoviera, Peter Varša, 'Deciding whether four perfect matchings can cover the edges of a snark is NP-complete', Theoretical Computer Science 988 (2024) 114374, DOI 10.1016/j.tcs.2023.114374, https://doi.org/10.1016/j.tcs.2023.114374
6. Ján Karabáš, Edita Máčajová, Roman Nedela, Martin Škoviera, 'Berge's Conjecture for Cubic Graphs With Small Colouring Defect', Journal of Graph Theory 109 (2025) 387-396, DOI 10.1002/jgt.23231; arXiv:2210.13234, https://arxiv.org/abs/2210.13234
7. Ján Karabáš, Edita Máčajová, Roman Nedela, Martin Škoviera, 'Cubic graphs of colouring defect 3 and conjectures of Berge and Alon-Tarsi', arXiv:2505.17569 (2025), https://arxiv.org/abs/2505.17569
8. Marién Abreu, Tomáš Kaiser, Domenico Labbate, Giuseppe Mazzuoccolo, 'Treelike Snarks', Electronic Journal of Combinatorics 23 (2016) #P3.54, DOI 10.37236/6008, https://doi.org/10.37236/6008
9. Noga Alon, Michael Tarsi, 'Covering Multigraphs by Simple Circuits', SIAM Journal on Algebraic Discrete Methods 6 (1985) 345-350, DOI 10.1137/0606035, https://doi.org/10.1137/0606035
10. G. H. Fan, A. Raspaud, 'Fulkerson's Conjecture and Circuit Covers', Journal of Combinatorial Theory, Series B 61 (1994) 133-138, DOI 10.1006/jctb.1994.1039, https://doi.org/10.1006/jctb.1994.1039
11. Jonas Hägglund, Klas Markstrøm, 'Shortest cycle covers and cycle double covers with large 2-regular subgraphs', Journal of Combinatorics 4 (2013) 457-468, DOI 10.4310/JOC.2013.v4.n4.a5; arXiv:1306.3088, https://arxiv.org/abs/1306.3088
12. Edita Máčajová, Martin Škoviera, 'Perfect Matching Index versus Circular Flow Number of a Cubic Graph', SIAM Journal on Discrete Mathematics 35 (2021) 1287-1297, DOI 10.1137/20M1359407; arXiv:2008.04775, https://arxiv.org/abs/2008.04775
13. Davide Mattiolo, Eckhard Steffen, 'Edge colorings and circular flows on regular graphs', Journal of Graph Theory 99 (2022) 399-413, DOI 10.1002/jgt.22746; arXiv:2001.02484, https://arxiv.org/abs/2001.02484
14. Jean Paul Zerafa, 'Ban–Linial's Conjecture and treelike snarks', Journal of Graph Theory 101 (2022) 511-520, DOI 10.1002/jgt.22837; arXiv:2102.07667, https://arxiv.org/abs/2102.07667
15. Xiaoyu Li, Rong-Xia Hao, Yilun Luo, Siyan Liu, 'Ban-Linial's Conjecture and Halin Snarks', Journal of Graph Theory (2026), DOI 10.1002/jgt.70080, https://doi.org/10.1002/jgt.70080
16. Robert Lukoťka, Makuochukwu F. Oguagbaka, 'Perfect versus imperfect matching covers of cubic graphs', Procedia Computer Science 273 (2025) 207-214, DOI 10.1016/j.procs.2025.10.300, https://doi.org/10.1016/j.procs.2025.10.300
17. Ján Karabáš, Edita Máčajová, 'On 4-covers of cubic graphs with two adjacent odd circuits in a 2-factor', arXiv:2605.09475 (2026), https://arxiv.org/abs/2605.09475
18. Sang-il Oum, 'A proof of the cycle double cover conjecture by OpenAI: An exposition', arXiv:2607.16356 (2026), https://arxiv.org/abs/2607.16356
19. Edita Máčajová, Giuseppe Mazzuoccolo, Gloria Tabarelli, 'Cycle separating cuts in possible counterexamples to the cycle double cover and the Berge-Fulkerson conjectures', Ars Mathematica Contemporanea 26 (2026) #P2.03, DOI 10.26493/1855-3974.3409.c13, https://doi.org/10.26493/1855-3974.3409.c13
20. D. R. Fulkerson, 'Blocking and anti-blocking pairs of polyhedra', Mathematical Programming 1 (1971) 168-194, DOI 10.1007/BF01584085, https://doi.org/10.1007/BF01584085
21. Giuseppe Mazzuoccolo, 'The equivalence of two conjectures of Berge and Fulkerson', Journal of Graph Theory 68 (2011) 125-128, DOI 10.1002/jgt.20545, https://doi.org/10.1002/jgt.20545