RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2008, том 5, страницы 255–278 (Mi semr105)

Эта публикация цитируется в 1 статье

Статьи

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

Аннотация: 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.

Ключевые слова: planar graphs, vertex coloring, chromatic number, $4$-critical graphs, Grötzsch–Sachs graphs.

УДК: 519.17

MSC: 05C15

Поступила 12 марта 2008 г., опубликована 10 июня 2008 г.

Язык публикации: английский



Реферативные базы данных:


© МИАН, 2024