Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Seminár z teórie grafov - Martin Škoviera (28.9.2023)

vo štvrtok 28.9.2023 o 9:50 hod. v Skleníku v pavilóne F1


25. 09. 2023 14.09 hod.
Od: Martin Škoviera

Prednášajúci: Martin Škoviera

Názov: Perfect-matching covers of cubic graphs with colouring defect 3

Termín: 28.9.2023, 9:50 hod., Skleník


Abstrakt:
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.

Stránka seminára