Perfect-matching covers of cubic graphs with colouring defect 3
Ján Karabáš, Edita Máčajová, Roman Nedela, Martin Škoviera · 2023
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.