Colouring defect of strong snarks

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F25%3A43978064" target="_blank" >RIV/49777513:23520/25:43978064 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.sciencedirect.com/science/article/pii/S1877050925036397?via%3Dihub" target="_blank" >https://www.sciencedirect.com/science/article/pii/S1877050925036397?via%3Dihub</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.procs.2025.10.292" target="_blank" >10.1016/j.procs.2025.10.292</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Colouring defect of strong snarks

Popis výsledku v původním jazyce

A strong snark is a 2-connected cubic graph which is not 3-edge-colourable and remains so after deleting any edge and suppressing the resulting 2-valent vertices. Strong snarks were introduced by Jaeger in 1985 as a class of cubic graphs that might include counterexamples to the cycle double cover conjecture, the 5-flow conjecture, or to other related longstanding conjectures. With these conjectures still widely open, strong snarks merit further investigation. In this paper we study colouring defect of strong snarks, an invariant introduced by Steffen in 2015 as the minimum number of edges of a cubic graph left uncovered by any set of three perfect matchings. This invariant provides one of measures of edge uncolourability of cubic graphs recently studied by several authors. Our main result shows that the colouring defect of a strong snark is at least 6, and that the bound is sharp.

Název v anglickém jazyce

Colouring defect of strong snarks

Popis výsledku anglicky

A strong snark is a 2-connected cubic graph which is not 3-edge-colourable and remains so after deleting any edge and suppressing the resulting 2-valent vertices. Strong snarks were introduced by Jaeger in 1985 as a class of cubic graphs that might include counterexamples to the cycle double cover conjecture, the 5-flow conjecture, or to other related longstanding conjectures. With these conjectures still widely open, strong snarks merit further investigation. In this paper we study colouring defect of strong snarks, an invariant introduced by Steffen in 2015 as the minimum number of edges of a cubic graph left uncovered by any set of three perfect matchings. This invariant provides one of measures of edge uncolourability of cubic graphs recently studied by several authors. Our main result shows that the colouring defect of a strong snark is at least 6, and that the bound is sharp.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

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 statě ve sborníku

Procedia Computer Science

ISBN

—

ISSN

1877-0509

e-ISSN

—

Počet stran výsledku

7

Strana od-do

149-155

Název nakladatele

Elsevier B.V.

Místo vydání

Amsterdam

Místo konání akce

Buenos Aires

Datum konání akce

10. 11. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—