Cubic graphs with colouring defect 3 (Q6126449)
From MaRDI portal
scientific article; zbMATH DE number 7829423
Language | Label | Description | Also known as |
---|---|---|---|
English | Cubic graphs with colouring defect 3 |
scientific article; zbMATH DE number 7829423 |
Statements
Cubic graphs with colouring defect 3 (English)
0 references
9 April 2024
0 references
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.
0 references
Fano flows
0 references
triples of perfect matchings
0 references