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/

[1] Dobrynin A. A., Mel'nikov L. S., “Counterexamples to Grotzsch–Sachs–Koester's conjecture”, Discrete Math., 306 (2006), 591–594 | DOI | MR | Zbl

[2] Dobrynin A. A., Mel'nikov L. S., “Grötzsch–Sachs graphs”, Abstracts of the Russian Conference Dedicated to the Fiftieth Anniversary of the Sobolev Institute of Mathematics “Mathematics in the Modern World” (September 17–23, 2007, Novosibirsk), 264–265 (in Russian)

[3] Dobrynin A. A., Mel'nikov L. S., “Infinite families of 4-chromatic Grötzsch–Sachs graphs”, J. Graph Theory, accepted | MR

[4] Dobrynin A. A., Mel'nikov L. S., “4-chromatic edge critical Grötzsch–Sachs graphs”, Discrete Math., accepted | MR

[5] Proc. Conference on Graph Theory (Eyba, 1984), ed. Sachs H., B. G. Teubner Verlagsgesellschaft, 1985 | MR

[6] Jaeger F., “On nowhere-zero flows in multigraphs”, Proceedings of the Fifth British Combinatorial Conference (University of Aberdeen, Aberdeen, July 14–18, 1975), Congressus Numerantium, 15, Utilitas Mathematica, Publising Inc., Winnipeg, 1976, 682–683 | MR

[7] Jaeger F., “Sur les graphes couverts par leurs bicycles et la conjecture des quatre couleurs”, Problèmes Combinatoires et Theorie des Graphes, Colloq. Internat. CNRS, 260, eds. Bermond J.-C., Fournier J.-C., Las Vergnas M., Sotteau D., CNRS, Paris, 1978, 243–247 | MR | Zbl

[8] Jaeger F., Sachs H., “Problem 4”, Graph Theory in memory of G. A. Dirac, Ann. Discrete Math., 41, eds. Andersen L. D., Jakobsen I. T., Thomassen C., Toft B., Vestergaard P. D., 1989, 515 | MR

[9] Jensen T., Toft B., Graph Coloring Problems, John Wiley Sons, New York, 1995 | MR | Zbl

[10] Koester G., “Bemerkung zu einem Problem von H. Grötzsch”, Wiss. Z. Univ. Halle, 33 (1984), 129 | Zbl

[11] Koester G., “Coloring problems on a class of 4-regular planar graphs”, Graphs, Hypergraphs and Applications, Proc. Conference on Graph Theory (Eyba, 1984), ed. Sachs H., B. G. Teubner Verlagsgesellschaft, 1985, 102–105 | MR | Zbl

[12] Koester G., “Note to a problem of T. Gallai and G. A. Dirac”, Combinatorica, 5 (1985), 227–228 | DOI | MR | Zbl

[13] Mel'nikov L. S., “Families of plane 4-regular 4-critical graphs”, Diskretn. Anal. Issled. Oper. Ser. 2, 11:1 (2004), 79–115 (in Russian) | MR

[14] Mel'nikov L. S., Dobrynin A. A., Koester G., “4-chromatic Grotzsch-Sachs graphs and edge- 4-critical 4-valent planar graphs, some remarks to older and latest results”, Abstracts of reports, Conference of Graph Theory on the Occasion of the 80th Birthday of Prof. Horst Sachs (March 27–30), Technical University Ilmenau, Germany, Ilmenau, 2007, 1

[15] Sachs H., “Problem”, Math. Balkanica, 4 (1974), 536 | MR | Zbl

[16] Sachs H., “A Three–Colour–Conjecture of Grötzsch”, Problèmes Combinatoires et Theorie des Graphes, eds. Bermond J.-C., Fournier J.-C., Las Vergnas M., Sotteau D., Editions du Centre National de la Recherche Scientifique, Paris, 1978, 441

[17] Steinberg R., “The state of the three color problem”, Quo Vadis, Graph Theory?, Annals Discrete Math., 55, eds. Gimbel J., Kennedy J. W., Quintas L. V., 1993, 211–248 | MR | Zbl