On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings (Q2922223)

There are many results and conjectures on covering graphs with perfect matchings and cycles (here a cycle means a subgraph with all degrees even). The Berge and Fulkerson conjecture states that the edge set of every cubic bridgeless graph can be covered by six perfect matchings, such that each edge is covered twice. The shortest cycle cover conjecture of Alon and Tarsi states that every bridgeless graph \(G\) has a cycle cover of length at most \(\frac{7}{5}|E(G)|\). This conjecture implies the famous cycle double cover conjecture, which states that every bridgeless graph has a cycle cover such that every edge is covered precisely twice. Snarks, which are non-3-edge-colorable cubic graphs with girth at least 5 and cyclically 4-edge-connected, play an important role in these conjectures.NEWLINENEWLINENEWLINEOne main contribution of this paper is the construction of an infinite family \(\mathcal{F}\) of snarks, whose edge set cannot be covered by four perfect matchings but it can be covered by five perfect matchings, i.e. of excessive index 5. This answers a question of \textit{J. L. Fouquet} and \textit{J. L. Vanherpe} [``On the perfect matching index of bridgeless cubic graphs'', Preprint, \url{arXiv:0904.1296}] asking whether the Pertersen graph is the unique snark having excessive index at least 5. The family \(\mathcal{F}\) is also of interests to cycle cover, for all graphs in it have shortest cycle cover of length greater than \(\frac{4}{3}|E(G)|\), which is a lower bound for cubic bridgeless graphs. The authors figure out a graph in \(\mathcal{F}\) whose shortest cycle cover has length at least \(\frac{4}{3}|E(G)|+2\), and further conjecture that there exist snarks in \(\mathcal{F}\) with shortest cycle cover of length larger than \(\frac{4}{3}|E(G)|\), which may provide some hints for the conjecture of \textit{G. Brinkmann} et al. [J. Comb. Theory, Ser. B 103, No. 4, 468--488 (2013; Zbl 1301.05119)] that every snark \(G\) has a cycle cover of size at most \((\frac{4}{3}+o(1))|E(G)|\).NEWLINENEWLINEDeciding whether a cubic bridgeless graph has excessive index 3 is NP-complete. Another contribution of the paper is a proof showing whether a cubic bridgeless graph having an excessive number at most 4 is also NP-complete.