Faculty of Mathematics, Physics
and Informatics
Comenius University in Bratislava

Seminar of Graph Theory - Martin Škoviera (15.3.2018)

Thursday 15.3.2018 at 9:50, Lecture room M/213


13. 03. 2018 10.30 hod.
By: Martin Škoviera

Martin Škoviera:
Smallest snarks with oddness 4


Abstract:

The oddness of a bridgeless cubic graph $G$ is the smallest number of odd circuits in a 2-factor of $G$. Oddness is one of the most important invariants of snarks because several important conjectures in graph theory can be reduced to snarks of oddness 4 or larger. In this talk we deal with the problem of determining the smallest order of a nontrivial snark of oddness 4. (Here `nontrivial' means girth at least 5 and cyclic connectivity at least 4.) We prove that the smallest order of a nontrivial snark with oddness 4 and cyclic connectivity 4 is 44, and characterise all snarks of order 44 with this property. The proof relies on a detailed analysis of 3-edge-colourings conflicting on a cycle-separating 4-edge-cut, an extensive computer search, and a closure theorem for cubic graphs with cyclic connectivity 4 due to Andersen, Fleischner, and Jackson (1988).

This is a joint work with Jan Goedgebeur and Edita Mačajová.