Cubic graphs with colouring defect 3
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F24%3A43971932" target="_blank" >RIV/49777513:23520/24:43971932 - isvavai.cz</a>
Result on the web
<a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v31i2p6" target="_blank" >https://www.combinatorics.org/ojs/index.php/eljc/article/view/v31i2p6</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.37236/12333" target="_blank" >10.37236/12333</a>
Alternative languages
Result language
angličtina
Original language name
Cubic graphs with colouring defect 3
Original language description
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, which provide the main motivation for our research.
Czech name
—
Czech description
—
Classification
Type
J<sub>SC</sub> - Article in a specialist periodical, which is included in the SCOPUS database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Electronic Journal of Combinatorics
ISSN
1097-1440
e-ISSN
1077-8926
Volume of the periodical
31
Issue of the periodical within the volume
2
Country of publishing house
US - UNITED STATES
Number of pages
32
Pages from-to
1-32
UT code for WoS article
—
EID of the result in the Scopus database
2-s2.0-85189897462