Geodesic
Two series of edge-$4$-critical Gr\"otzsch--Sachs graphs generated by four curves in the plane
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 5 (2008), pp. 255-278

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{SEMR_2008_5_a19,
     author = {A. A. Dobrynin and L. S. Mel'nikov},
     title = {Two series of edge-$4$-critical {Gr\"otzsch--Sachs} graphs generated by four curves in the plane},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {255--278},
     publisher = {mathdoc},
     volume = {5},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2008_5_a19/}
}
TY  - JOUR
AU  - A. A. Dobrynin
AU  - L. S. Mel'nikov
TI  - Two series of edge-$4$-critical Gr\"otzsch--Sachs graphs generated by four curves in the plane
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2008
SP  - 255
EP  - 278
VL  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2008_5_a19/
LA  - en
ID  - SEMR_2008_5_a19
ER  - 
%0 Journal Article
%A A. A. Dobrynin
%A L. S. Mel'nikov
%T Two series of edge-$4$-critical Gr\"otzsch--Sachs graphs generated by four curves in the plane
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2008
%P 255-278
%V 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2008_5_a19/
%G en
%F SEMR_2008_5_a19
A. A. Dobrynin; L. S. Mel'nikov. Two series of edge-$4$-critical Gr\"otzsch--Sachs graphs generated by four curves in the plane. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 5 (2008), pp. 255-278. http://geodesic.mathdoc.fr/item/SEMR_2008_5_a19/