Covering cubic graphs with matchings of large size (Q2848743)

An \([m]\)-matching is a matching with \(m\) pairs. The excessive \([m]\)-index of a graph \(G\), denoted by \(\chi_{[m]}^\prime(G)\) (cf. [\textit{D. Cariolaro} and \textit{H.-L. Fu}, Discrete Math. 310, No. 2, 276--287 (2010; Zbl 1243.05192)]) is the minimum number of \([m]\)-matchings needed to cover the edges of \(G\).NEWLINENEWLINE Proposition 1. Let \(G\) be a cubic graph of order \(2n\). If \(m<\frac{3n}4\), then \(\chi_{[m]}^\prime(G)=\left\lceil\frac{3n}m\right\rceil\).NEWLINENEWLINE Proposition 2. For every positive integer \(m\) there exists a positive integer \(n\) and a cubic graph \(G\) of order \(2n\) such that \(\chi_{[n-1]}^\prime(G)\geq m\).NEWLINENEWLINE Proposition 3. Let \(G\) be a 3-edge-colourable cubic graph of order \(2n\geq8\). Then \(\chi_{[n-1]}^\prime(G)=4.\) The second author has proved [J. Graph Theory 68, No. 2, 125--128 (2011; Zbl 1230.05238)] that a conjecture of Berge and Fulkerson [\textit{D. R. Fulkerson}, Math. Program. 1, 168--194 (1971; Zbl 0254.90054)] can be expressed as Conjecture 2. If \(G\) is a 3-graph of order \(2n\), then \(\chi_{[n]}^\prime(G)\leq5\).NEWLINENEWLINE Proposition 4. The Berge-Fulkerson conjecture implies that \(\chi_{[n-1]}^\prime(G)\leq5\) for each cubic graph \(G\) of order exceeding 4.NEWLINENEWLINE A snark is a cyclically 4-connected non-3-edge-colourable cubic graph of girth at least 5.NEWLINENEWLINE Proposition 5. Let \(G\) be a snark of order \(2n\leq32\). Then \(\chi_{[n-1]}^\prime(G)=4\).NEWLINENEWLINE The oddness of a cubic graph is the minimum number of odd circuits in a 2-factor.NEWLINENEWLINE Proposition 6. Let \(G\) be a cubic graph of order \(2n\) and oddness 2. Then \(\chi_{[n-1]}^\prime(G)=4\).NEWLINENEWLINE Proposition 7. Let \(G\) be a cyclically 4-connected cubic graph of order \(2n\) and oddness 4. Then \(\chi_{[n-1]}^\prime(G)=4\).NEWLINENEWLINE A cubic graph \(G\) is \(3^*\)-connected if it has vertices \(a,b\) which are the end-vertices of three openly disjoint paths \(Q_1\), \(Q_2\), \(Q_3\) such that \(V(G)=\bigcup\limits^3_{i=1}V(Q_i)\) [\textit{M. Albert} et al., Australas. J. Comb. 24, 193--207 (2001; Zbl 0982.05062)].NEWLINENEWLINE Proposition 8. Let \(G\) be a \(3^*\)-connected cubic graph of order \(2n\), with \(n\geq4\). Then \(\chi_{n-1}^\prime(G)=4\).NEWLINENEWLINE Proposition 9. Let \(G\) be a cubic graph of order \(2n\geq8\) and longest circuit at least \(2n-2\). Then \(\chi_{[n-1]}^\prime(G)=4\).NEWLINENEWLINE (Caveat lector! Some apparent misprints have been corrected in the preceding list of propositions.)