Seminár z teórie grafov - Ján Karabáš (14.5.2026)
vo štvrtok 14.5.2026 o 9:50 hod. v miestnosti M 213
Prednášajúci: Ján Karabáš (FEI STU Bratislava)
Názov prednášky: Colouring defect of strong snarks
Termín: 14.5.2026, 9:50 hod., M 213
Abstrakt:
A strong snark is a 2-connected cubic graph which is not 3-edge-colourable and remains so after deleting any edge and by suppressing the resulting 2-valent vertices. Strong snarks were introduced by Jaeger in 1985 as a class of cubic graphs that might include counterexamples to the cycle double conjecture, the 5-flow conjecture, or to other related longstanding conjectures. With these conjectures still widely open, strong snarks merit further investigation. In this paper we study colouring defect of strong snarks, an invariant introduced by Steffen in 2015 as the minimum number of edges of a cubic graph left uncovered by any set of three perfect matchings. This invariant provides one of measures of edge uncolourability of cubic graphs recently studied by several authors. Our main result shows that the colouring defect of a strong snark is at least 6, and the bound is best possible.
(Joint work with E. Macajova, R. Nedela, and M. Skoviera.)