|
Сибирские электронные математические известия, 2008, том 5, страницы 255–278
(Mi semr105)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 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.
Поступила 12 марта 2008 г., опубликована 10 июня 2008 г.
Образец цитирования:
A. A. Dobrynin, L. S. Mel'nikov, “Two series of edge-$4$-critical Grötzsch–Sachs graphs generated by four curves in the plane”, Сиб. электрон. матем. изв., 5 (2008), 255–278
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr105 https://www.mathnet.ru/rus/semr/v5/p255
|
Статистика просмотров: |
Страница аннотации: | 287 | PDF полного текста: | 58 | Список литературы: | 55 |
|