Seminár z teórie grafov - Martin Škoviera (15.3.2018)

vo štvrtok 15.3.2018 o 9:50 hod. v miestnosti M/213

---

Prednášajúci: Martin Škoviera

Názov: Smallest snarks with oddness 4

Termín: 15.3.2018, 9:50 hod., M/213

Abstrakt:
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á.  

---