|
Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2008, Volume 5, Pages 255–278
(Mi semr105)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Research papers
Two series of edge-$4$-critical Grötzsch–Sachs graphs generated by four curves in the plane
A. A. Dobrynina, L. S. Mel'nikovab a Sobolev Institute of Mathematics, Novosibirsk, Russia
b Novosibirsk State University
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 a graph $G$ arises as a superposition of simple closed curves in the plane with tangencies disallowed. Graphs of this class are called Grötzsch–Sachs graphs. Two infinite families of
edge-$4$-critical Grötzsch–Sachs graphs generated by four curves in the plane have been announced in [4]. In this paper, we present a complete proof of this result.
Keywords:
planar graphs, vertex coloring, chromatic number, $4$-critical graphs, Grötzsch–Sachs graphs.
Received March 12, 2008, published June 10, 2008
Citation:
A. A. Dobrynin, L. S. Mel'nikov, “Two series of edge-$4$-critical Grötzsch–Sachs graphs generated by four curves in the plane”, Sib. Èlektron. Mat. Izv., 5 (2008), 255–278
Linking options:
https://www.mathnet.ru/eng/semr105 https://www.mathnet.ru/eng/semr/v5/p255
|
Statistics & downloads: |
Abstract page: | 276 | Full-text PDF : | 56 | References: | 50 |
|