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

03. 10. 2018 10.33 hod.
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

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