Seminar of Graph Theory - Martin Škoviera (15.3.2018)
Thursday 15.3.2018 at 9:50, Lecture room M/213
By: Martin Škoviera
Smallest snarks with oddness 4
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á.