RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2008 Volume 5, Pages 255–278 (Mi semr105)

This article is cited 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.

UDC: 519.17

MSC: 05C15

Received March 12, 2008, published June 10, 2008

Language: English



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024