Short cycle covers and the colouring defect of a cubic graph

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Short cycle covers and the colouring defect of a cubic graph
Original language description
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.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Similar results(10)