Seminar of Graph Theory - Jozef Rajnik (21.11.2019)

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

19. 11. 2019 12.41 hod.
By: Martin Škoviera

Jozef Rajník:
Constructions of critical and strictly critical snarks

Abstract:
Critical snarks are non-3-edge-colourable cubic graphs such that the removal of any two adjacent vertices leaves a 3-edge-colourable graph. A vast majority of them is also bicritical -- i.e. removing any two vertices leaves a colourable graph. Therefore, critical snarks that are not bicritical form a rather interesting class of snarks -- they are called strictly critical snarks and were studied by Chladný and Škoviera along with their relation to bicriticality of cyclically 4-connected snarks. Inspired by the analysis of small cases, we construct an infinite family of strictly critical snarks with girth 6. Furthermore, by proving that a certain type of superposition preserves criticality, we construct an infinite class of cyclically 6-connected strictly critical snarks, which solves a problem proposed by Chladný and Škoviera.