Short cycle covers and the colouring defect of a cubic graph

Kód výsledku v IS VaVaI

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

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Short cycle covers and the colouring defect of a cubic graph

Popis výsledku v původním jazyce

A longstanding conjecture of Alon and Tarsi, and indepentry Jaeger (1985), suggests that the edges of every bridgeless graph can be covered with cycles of total length at most 7/5 •m, where m is the number of edges. We study the relationship between cycle covers and structural properties of cubic graphs, focusing on their colouring defect. This invariant, introduced by Steffen in 2015, is defined as the minimum number of edges left uncovered by any set of three perfect matchings of a cubic graph. We show that every bridgeless cubic graph with colouring defect not exceeding 3 admits a cycle cover of length at most 4/3 •m + 1, just one step above the universal lower bound of 4/3 •m for all cubic graphs. We also prove that, regardless of defect, the same bound holds for bridgeless cubic graphs that have an edge whose end vertices removed yield a 3-edge-colourable graph and the edge lies on a 5-cycle. Motivated by our investigations, we introduce a new invariant for cubic graphs, their covering excess, to measure the deviation of the length of a shortest cycle cover from the mentioned lower bound. Finally, we show that every bridgeless cubic graph with covering excess at most 1 admits a cycle double cover.

Název v anglickém jazyce

Short cycle covers and the colouring defect of a cubic graph

Popis výsledku anglicky

A longstanding conjecture of Alon and Tarsi, and indepentry Jaeger (1985), suggests that the edges of every bridgeless graph can be covered with cycles of total length at most 7/5 •m, where m is the number of edges. We study the relationship between cycle covers and structural properties of cubic graphs, focusing on their colouring defect. This invariant, introduced by Steffen in 2015, is defined as the minimum number of edges left uncovered by any set of three perfect matchings of a cubic graph. We show that every bridgeless cubic graph with colouring defect not exceeding 3 admits a cycle cover of length at most 4/3 •m + 1, just one step above the universal lower bound of 4/3 •m for all cubic graphs. We also prove that, regardless of defect, the same bound holds for bridgeless cubic graphs that have an edge whose end vertices removed yield a 3-edge-colourable graph and the edge lies on a 5-cycle. Motivated by our investigations, we introduce a new invariant for cubic graphs, their covering excess, to measure the deviation of the length of a shortest cycle cover from the mentioned lower bound. Finally, we show that every bridgeless cubic graph with covering excess at most 1 admits a cycle double cover.

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

156-162

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

—