Girth, oddness, and colouring defect of snarks
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F22%3A43965518" target="_blank" >RIV/49777513:23520/22:43965518 - isvavai.cz</a>
Výsledek na webu
<a href="https://www.sciencedirect.com/journal/discrete-mathematics" target="_blank" >https://www.sciencedirect.com/journal/discrete-mathematics</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.disc.2022.113040" target="_blank" >10.1016/j.disc.2022.113040</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Girth, oddness, and colouring defect of snarks
Popis výsledku v původním jazyce
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 2factor. 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 g >= 5, not just girth at least g.
Název v anglickém jazyce
Girth, oddness, and colouring defect of snarks
Popis výsledku anglicky
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 2factor. 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 g >= 5, not just girth at least g.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2022
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ů
Údaje specifické pro druh výsledku
Název periodika
DISCRETE MATHEMATICS
ISSN
0012-365X
e-ISSN
1872-681X
Svazek periodika
345
Číslo periodika v rámci svazku
11
Stát vydavatele periodika
NL - Nizozemsko
Počet stran výsledku
10
Strana od-do
nestrankovano
Kód UT WoS článku
000818515100013
EID výsledku v databázi Scopus
2-s2.0-85132327227