Seminar of Graph Theory - Martin Škoviera (28.9.2023)
Thursday 28.9.2023 at 9:50 hod., Lecture room Skleník
Martin Škoviera:
Perfect-matching covers of cubic graphs with colouring defect 3
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.
This is a joint work with Ján Katabáš, Edita Máčajová, and Roman Nedela.