Geodesic
4-chromatic Koester graphs
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 617-627

Voir la notice de l'article provenant de la source Library of Science

Let G be a simple 4-regular plane graph and let S be a decomposition of G into edge-disjoint cycles. Suppose that every two adjacent edges on a face belong to different cycles of S. Such a graph G arises as a superposition of simple closed curves in the plane with tangencies disallowed. Studies of coloring of graphs of this kind were originated by Grötzsch. Two 4-chromatic graphs generated by circles in the plane were constructed by Koester in 1984 [10,11,12]. Until now, no other examples of such graphs were known. We present fourteen new 4-chromatic graphs generated by circles in the plane.
Keywords: planar graph, 4-critical graph, Grötzsch-Sachs graph, Koester graph 
@article{DMGT_2012_32_4_a1,
     author = {Dobrynin, Andrey and Mel'nikov, Leonid},
     title = {4-chromatic {Koester} graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {617--627},
     publisher = {mathdoc},
     volume = {32},
     number = {4},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a1/}
}
TY  - JOUR
AU  - Dobrynin, Andrey
AU  - Mel'nikov, Leonid
TI  - 4-chromatic Koester graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 617
EP  - 627
VL  - 32
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a1/
LA  - en
ID  - DMGT_2012_32_4_a1
ER  - 
%0 Journal Article
%A Dobrynin, Andrey
%A Mel'nikov, Leonid
%T 4-chromatic Koester graphs
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 617-627
%V 32
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a1/
%G en
%F DMGT_2012_32_4_a1
Dobrynin, Andrey; Mel'nikov, Leonid. 4-chromatic Koester graphs. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 617-627. http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a1/