4-chromatic Koester graphs

Andrey A. Dobrynin; Leonid S. Mel'nikov

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 4, page 617-627
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Andrey A. Dobrynin, and Leonid S. Mel'nikov. "4-chromatic Koester graphs." Discussiones Mathematicae Graph Theory 32.4 (2012): 617-627. <http://eudml.org/doc/271063>.

@article{AndreyA2012,
abstract = {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.},
author = {Andrey A. Dobrynin, Leonid S. Mel'nikov},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {planar graph; 4-critical graph; Grötzsch-Sachs graph; Koester graph},
language = {eng},
number = {4},
pages = {617-627},
title = {4-chromatic Koester graphs},
url = {http://eudml.org/doc/271063},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Andrey A. Dobrynin
AU - Leonid S. Mel'nikov
TI - 4-chromatic Koester graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 4
SP - 617
EP - 627
AB - 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.
LA - eng
KW - planar graph; 4-critical graph; Grötzsch-Sachs graph; Koester graph
UR - http://eudml.org/doc/271063
ER -

References

top
  1. [1] A.A. Dobrynin and L.S. Mel'nikov, Counterexamples to Grötzsch-Sachs-Koester's conjecture, Discrete Math. 306 (2006) 591-594, doi: 10.1016/j.disc.2005.08.010. Zbl1088.05030
  2. [2] A.A. Dobrynin and L.S. Mel'nikov, Two series of edge 4-critical Grötzsch-Sachs graphs generated by four curves in the plane, Siberian Electronic Math. Reports 5 (2008) 255-278. Zbl1299.05121
  3. [3] A.A. Dobrynin and L.S. Mel'nikov, Infinite families of 4-chromatic Grötzsch-Sachs graphs, J. Graph Theory 59 (2008) 279-292, doi: 10.1002/jgt.20339. Zbl1223.05067
  4. [4] A.A. Dobrynin and L.S. Mel'nikov, 4-chromatic edge critical Grötzsch-Sachs graphs, Discrete Math. 309 (2009) 2564-2566, doi: 10.1016/j.disc.2008.06.006. Zbl1221.05135
  5. [5] H. Sachs (Ed.), Graphs, Hypergraphs and Applications, Proc. Conference on Graph Theory, Eyba, 1984, (B.G. Teubner Verlagsgesellschaft, 1985). 
  6. [6] F. Jaeger, On nowhere-zero flows in multigraphs, Proc. Fifth British Combinatorial Conference 1975, C.St.J.A. Nash-Williams and J.Sheehan (Ed(s)), (Congressus Numerantium XV, Winnipeg, Utilitas Mathematica Publising, Inc. 1976) 373-378. 
  7. [7] F. Jaeger, Sur les graphes couverts par leurs bicycles et la conjecture des quatre couleurs, in: Probl`emes Combinatoires et Theorie des Graphes, J.-C. Bermond, J.- C. Fournier, M. Las Vergnas and D. Sotteau (Ed(s)), (Paris, Editions du Centre National de la Recherche Scientifique, 1978) 243–247. Zbl0412.05044
  8. [8] F. Jaeger and H. Sachs, Problem, in: Graph Theory in memory of G.A. Dirac, ed(s), L.D. Andersen, I.T. Jakobsen, C. Thomassen, B. Toft, P.D. Vestergaard Ann. Discrete Math. 41, 1989) 515. 
  9. [9] T. Jensen and B. Toft, Graph Coloring Problems (John Wiley & Sons, New York, 1995). 
  10. [10] G. Koester, Bemerkung zu einem Problem von H. Grötzsch, Wiss. Z. Univ. Halle 33 (1984) 129. 
  11. [11] G. Koester, Coloring problems on a class of 4-regular planar graphs, in: Graphs, Hypergraphs and Applications. Proc. Conference on Graph Theory, Eyba, 1984, ed(s), H. Sachs B.G. Teubner Verlagsgesellschaft, 1985) 102-105. 
  12. [12] G. Koester, Note to a problem of T. Gallai and G. A. Dirac, Combinatorica 5 (1985) 227-228, doi: 10.1007/BF02579365. Zbl0593.05030
  13. [13] L.S. Mel’nikov, A.A. Dobrynin and G. Koester, 4-chromatic Grötzsch-Sachs graphs and edge 4-critical 4-valent planar graphs, some remarks on older and latest results, Report on Conf. Graph Theory on the Occasion of the 80th Birthday of Prof. Horst Sachs (Technical University Ilmenau, Germany, Ilmenau, March, 2007). 
  14. [14] H. Sachs, Problem, Math. Balkanica 4 (1974) 536. 
  15. [15] H. H. Sachs, A Three-Colour-Conjecture of Grötzsch, in: Probl`emes Combinatoires et Theorie des Graphes, J.-C. Bermond, J.-C. Fournier, M. Las Vergnas and D. Sotteau (Ed(s)), (Paris, Editions du Centre National de la Recherche Scientifique, 1978) 441. 
  16. [16] R. Steinberg, The state of the three color problem, in: Quo Vadis, Graph Theory?, ed(s), J. Gimbel, J.W. Kennedy, L.V. Quintas Annals Discrete Math. 55, 1993) 211-248. Zbl0791.05044

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.