Cubic graphs with colouring defect 3

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Cubic graphs with colouring defect 3

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Cubic graphs with colouring defect 3

Popis výsledku anglicky

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.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Electronic Journal of Combinatorics

ISSN

1097-1440

e-ISSN

1077-8926

Svazek periodika

31

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

32

Strana od-do

1-32

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85189897462