Seminár z teórie grafov - Edita Mačajová (4.10.2018)
vo štvrtok 4.10.2018 o 9:50 hod. v miestnosti M/213
Od: Martin Škoviera
Prednášajúci: Edita Mačajová
Názov: Smallest nontrivial snarks of oddness 4
Termín: 4.10.2018, 9:50 hod., M/213
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)