Girth, oddness, and colouring defect of snarks

DOI10.1016/J.DISC.2022.113040MaRDI QIDQ2166293zbMATH OpenOpenAlexFDO

Authors Ján Karabáš, E. Máčajová, Roman Nedela, Martin Škoviera

Publication date 24 August 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.12205

zbMATH Keywords

girthoddnesssnarkcolouring defect

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: The colouring defect of a cubic graph, introduced by Steffen in 2015, is the minimum number of edges that are left uncovered by any set of three perfect matchings. Since a cubic graph has defect $0$ if and only if it is $3$-edge-colourable, this invariant can measure how much a cubic graph differs from a $3$-edge-colourable graph. Our aim is to examine the relationship of colouring defect to oddness, an extensively studied measure of uncolourability of cubic graphs, defined as the smallest number of odd circuits in a $2$-factor. We show that there exist cyclically $5$-edge-connected snarks (cubic graphs with no $3$-edge-colouring) of oddness $2$ and arbitrarily large colouring defect. This result is achieved by means of a construction of cyclically $5$-edge-connected snarks with oddness $2$ and arbitrarily large girth. The fact that our graphs are cyclically $5$-edge-connected significantly strengthens a similar result of Jin and Steffen (2017), which only guarantees graphs with cyclic connectivity at most $3$. At the same time, our result improves Kochol's original construction of snarks with large girth (1996) in that it provides infinitely many nontrivial snarks of any prescribed girth $gge5$, not just girth at least~$g$.

Recommendations

• The smallest nontrivial snarks of oddness 4
• Snarks without small cycles
• Relating embedding and coloring properties of snarks
• Snarks with large oddness and small number of vertices
• Small snarks with large oddness

Cites work

• scientific article; zbMATH DE number 3937197 (Why is no real title available?)
• scientific article; zbMATH DE number 874369 (Why is no real title available?)
• scientific article; zbMATH DE number 3390835 (Why is no real title available?)
• 1-factor and cycle covers of cubic graphs
• Classification and characterizations of snarks
• Decomposition of snarks
• Decompositions and reductions of snarks
• Fulkerson's conjecture and circuit covers
• Intersecting 1-factors and nowhere-zero 5-flows
• Measurements of edge-uncolorability
• Measures of edge-uncolorability of cubic graphs
• Petersen cores and the oddness of cubic graphs
• Reduction of the Berge-Fulkerson conjecture to cyclically 5-edge-connected snarks
• Regular maps on surfaces with large planar width
• Small snarks with large oddness
• Snarks without small cycles
• Sparsely intersecting perfect matchings in cubic graphs
• Superposition and constructions of graphs without nowhere-zero k-flows
• Superposition of snarks revisited

Cited in

(3)

• Cubic graphs with colouring defect 3
• Snarks with large oddness and small number of vertices
• Relating embedding and coloring properties of snarks

This page was built for publication: Girth, oddness, and colouring defect of snarks

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