Perfect-matching covers of cubic graphs with colouring defect 3

EUROCOMB’23

Abstract
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 have defect at least $3$. We show that every bridgeless cubic graph with defect $3$ can have its edges covered with at most five perfect matchings, which verifies a long-standing conjecture of Berge for this class of graphs. Moreover, we determine the extremal graphs.

Pages:
639–646
References

] F. Chen and G. Fan. Fulkerson-covers of hypohamiltonian graphs. Discrete Appl. Math., 186:66-73, 2015.
https://doi.org/10.1016/j.dam.2015.01.009

M. A. Fiol, G. Mazzuoccolo, and E. Steffen. Measures of edge-uncolorability of cubic graphs. Electron. J. Combin., 25(P4.54), 2018.
https://doi.org/10.37236/6848

J.-L. Fouquet and J.-M. Vanherpe. On Fulkerson conjecture. Discuss. Math. Graph Theory, 31:253-272, 2011.
https://doi.org/10.7151/dmgt.1543

R.-X. Hao, X. Wang J. Niu, C.-Q. Zhang, and T. Zhang. A note on Berge-Fulkerson coloring. Discrete Math., 309:4235-4240, 2009.
https://doi.org/10.1016/j.disc.2008.12.024

R.-X. Hao, C.-Q. Zhang, and T. Zheng. Berge-Fulkerson coloring for $C_(8)$-linked graphs. J. Graph Theory, 88:46-60, 2018.
https://doi.org/10.1002/jgt.22184

R. Isaacs. Infinite families of non-trivial trivalent graphs which are not Tait colorable. Amer. Math. Monthly, 82:221-239, 1975.
https://doi.org/10.1080/00029890.1975.11993805

L. Jin, G. Mazzuoccolo, and E. Steffen. Cores, joins and the Fano-flow conjectures. Discuss. Math. Graph Theory, 38:165-175, 2018.
https://doi.org/10.7151/dmgt.1999

L. Jin and E. Steffen. Petersen cores and the oddness of cubic graphs. J. Graph Theory, 84:109-120, 2017.
https://doi.org/10.1002/jgt.22014

S. Liu, R.-X. Hao, and C.-Q. Zhang. Rotation snark, Berge-Fulkerson conjecture and Catlin's 4-flow reduction. Appl. Math. Comput., 410:126441, 2021.
https://doi.org/10.1016/j.amc.2021.126441

G. Mazzuoccolo. The equivalence of two conjectures of Berge and Fulkerson. J. Graph Theory, 68:125-128, 2011.
https://doi.org/10.1002/jgt.20545

J. Karabáš, E. Máčajová, R. Nedela, and M. Škoviera. Berge covers of cubic graphs with colouring defect 3. in preparation, 2022.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-088

J. Karabáš, E. Máčajová, R. Nedela, and M. Škoviera. Berge's conjecture for cubic graphs with small colouring defect. arXiv:2210.13234 [math.CO], 2022.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-088

J. Karabáš, E. Máčajová, R. Nedela, and M. Škoviera. Cubic graphs with colouring defect 3. manuscript, 2022.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-088

J. Karabáš, E. Máčajová, R. Nedela, and M. Škoviera. Girth, oddness, and colouring defect of snarks. Discrete Math., 345:113040, 2022.
https://doi.org/10.1016/j.disc.2022.113040

T. Schönberger. Ein Beweis des Petersenschen Graphensatzes. Acta Litt. Sci. Szeged, 7:51-57, 1934.

P. D. Seymour. On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte. London. Math. Soc., 38:423-460, 1979.
https://doi.org/10.1112/plms/s3-38.3.423

E. Steffen. 1-Factor and cycle covers of cubic graphs. J. Graph Theory, 78:195-206, 2015.
https://doi.org/10.1002/jgt.21798

Metrics

0

Views

0

PDF views