Cubic graphs with colouring defect 3

Coloring of graphs and hypergraphs (05C15) Flows in graphs (05C21) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Review text

Summary: The colouring defect of a cubic graph is the smallest number of edges left uncovered by any set of three perfect matchings. While \(3\)-edge-colourable graphs have defect \(0\), those that cannot be \(3\)-edge-coloured (that is, snarks) are known to have defect at least \(3\). In this paper we focus on the structure and properties of snarks with defect \(3\). For such snarks we develop a theory of reductions similar to standard reductions of short cycles and small cuts in general snarks. We prove that every snark with defect \(3\) can be reduced to a snark with defect \(3\) which is either nontrivial (cyclically \(4\)-edge-connected and of girth at least \(5)\) or to one that arises from a nontrivial snark of defect greater than \(3\) by inflating a vertex lying on a suitable \(5\)-cycle to a triangle. The proofs rely on a detailed analysis of Fano flows associated with triples of perfect matchings leaving exactly three uncovered edges. In the final part of the paper we discuss application of our results to the conjectures of Berge and Fulkerson (see [\textit{E. Máčajová} and \textit{G. Mazzuoccolo}, Proc. Am. Math. Soc. 148, No. 11, 4643--4652 (2020; Zbl 1447.05172)]), which provide the main motivation for our research.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Cubic graphs with colouring defect 3

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6126449)