Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

Seminar of Graph Theory - Martin Škoviera (28.9.2023)

Thursday 28.9.2023 at 9:50 hod., Lecture room Skleník

25. 09. 2023 14.17 hod.
By: Martin Škoviera

Martin Škoviera:
Perfect-matching covers of cubic graphs with colouring defect 3

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.

More information