Seminar of Graph Theory - Edita Mačajová (4.10.2018)
Thursday 4.10.2018 at 9:50, Lecture room M/213
By: Martin Škoviera
Smallest nontrivial snarks of oddness 4
The oddness of a cubic graph is the smallest number of odd circuits in a 2-factor of the graph. Oddness constitutes one of the most important measures of uncolourability of cubic graphs. In a previous talk (delivered earlier this year by M. Skoviera) we showed that the smallest number of vertices of a snark with cyclic connectivity 4 and oddness 4 is 44. In this talk we show that there are exactly 31 such snarks. These snarks are built up from subgraphs of the Petersen graph and a small number of additional vertices. Depending of their structure they fall into six classes. We indicate the reasons why these snarks have oddness 4 and sketch the proof that the 31 snarks form a complete set snarks with cyclic connectivity 4 and oddness 4 on 44 vertices.
(This is joint work with Jan Goedgebeur and Martin Skoviera)