Faculty of Mathematics, Physics
and Informatics
Comenius University in Bratislava

Seminar of Graph Theory - Edita Mačajová (4.10.2018)

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


03. 10. 2018 10.36 hod.
By: Martin Škoviera

Edita Mačajová:
Smallest nontrivial snarks of oddness 4


Abstract:
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)