Infinite families of 4‐chromatic Grötzsch‐Sachs graphs
Andrey A. Dobrynin, Leonid S. Mel’nikov · Journal of Graph Theory · 2008
Abstract Let G be a 4‐regular planar graph and suppose that G has a cycle decomposition S (i.e., each edge of G is in exactly one cycle of the decomposition) with every pair of adjacent edges on a face always in different cycles of S. Such graphs, called Grötzsch‐Sachs graphs, arise as a superposition of simple closed curves in the plane with tangencies disallowed. The first two known 4‐chromatic Grötzsch‐Sachs graphs of order 18 were reported in Dobrynin and Mel'nikov [Discrete Math 306 (2006), 591‐594]. In this article, all edge 4‐critical subgraphs of these graphs are described and infinite families of 4‐chromatic Grötzsch‐Sachs graphs with connectivity 2, 3, and 4 are constructed. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 279–292, 2008