Geodesic
Edge $4$-critical Koester graph of order $28$
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 2, pp. 847-853.

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

A Koester graph $G$ is a simple $4$-regular plane graph formed by the superposition of a set $S$ of circles in the plane, no two of which are tangent and no three circles have a common point. Crossing points and arcs of $S$ correspond to vertices and edges of $G$, respectively. A graph $G$ is edge critical if the removal of any edge decreases its chromatic number. A $4$–chromatic edge critical Koester graph of order $28$ generated by intersection of six circles is presented. This improves an upper bound for the smallest order of such graphs. The previous upper bound was established by Gerhard Koester in 1984 by constructing a graph with $40$ vertices.
Keywords: plane graph, $4$-critical graph, Grötzsch–Sachs graph, Koester graph. 
@article{SEMR_2023_20_2_a34,
     author = {A. A. Dobrynin},
     title = {Edge $4$-critical {Koester} graph of order $28$},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {847--853},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a34/}
}
TY  - JOUR
AU  - A. A. Dobrynin
TI  - Edge $4$-critical Koester graph of order $28$
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2023
SP  - 847
EP  - 853
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a34/
LA  - en
ID  - SEMR_2023_20_2_a34
ER  - 
%0 Journal Article
%A A. A. Dobrynin
%T Edge $4$-critical Koester graph of order $28$
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2023
%P 847-853
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a34/
%G en
%F SEMR_2023_20_2_a34
A. A. Dobrynin. Edge $4$-critical Koester graph of order $28$. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 2, pp. 847-853. http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a34/

[1] L. Beineke, R. Wilson, B. Toft (Eds.), Topics in chromatic graph theory, Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 2015 | MR | Zbl

[2] M.-K. Chiu, S. Felsner, M. Scheucher, F. Schröder, R. Steiner, B. Vogtenhuber, Coloring circle arrangements: New 4-chromatic planar graphs, 2022, arXiv: 2205.08181v1

[3] A.A. Dobrynin, “A new 4-chromatic edge critical Koester graph”, Discrete Math. Lett., 12 (2023), 6–10 | DOI | MR | Zbl

[4] A.A. Dobrynin, L.S. Mel'nikov, “Counterexamples to Grötzsch-Sachs-Koester's conjecture”, Discrete Math., 306:6 (2006), 591–594 | DOI | MR | Zbl

[5] A.A. Dobrynin, L.S. Mel'nikov, “Two series of edge-4-critical Grötzsch-Sachs graphs generated by four curves in the plane”, Sib. Èlektron. Mat. Izv., 5 (2008), 255–278 | MR | Zbl

[6] A.A. Dobrynin, L.S. Mel'nikov, “Infinite families of 4-chromatic Grötzsch-Sachs graphs”, J. Graph Theory, 59:4 (2008), 279–292 | DOI | MR | Zbl

[7] A.A. Dobrynin, L.S. Mel'nikov, Discrete Math., 309:8 (2009), 2564–2566 | DOI | MR | Zbl

[8] A.A. Dobrynin, L.S. Mel'nikov, “4-chromatic Koester graphs”, Discuss. Math. Graph Theory, 32:4 (2012), 617–627 | DOI | MR | Zbl

[9] F. Jaeger, “On nowhere-zero flows in multigraphs”, Proc. 5th Br. comb. Conf. (Aberdeen 1975), eds. C.St.J.A. Nash-Williams, J. Sheehan, Utilitas Mathematica Pub., Winnipeg, 1976, 373–378 | MR | Zbl

[10] F. Jaeger, “Sur les graphes couverts par leurs bicycles et la conjecture des quatre couleurs”, Problèmes combinatoires et theorie des graphes, eds. J.-C. Bermond, J.-C. Fournier, M. Las Vergnas, D. Sotteau, Editions du Centre National de la Recherche Scientifique, Paris, 1978, 243–247 | MR | Zbl

[11] F. Jaeger, H. Sachs, “Problems”, Graph Theory in Memory of G.A. Dirac, Ann. Discrete Math., 41, eds. L.D. Andersen, I.T. Jakobsen, C. Thomassen, B. Toft, P.D. Vestergaard, 1988, 515–517 | DOI | MR

[12] T. Jensen, B. Toft, Graph coloring problems, John Wiley Sons, New York, 1995 | MR | Zbl

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

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

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

[16] F. Runge, H. Sachs, “Berechnung der Anzahl der Gerüste von Graphen und Hypergraphen mittels deren Spektren”, Math. Balk., 4 (1974), 529–536 | MR | Zbl

[17] H. Sachs, “A three-colour-conjecture of Grötzsch”, Problèmes Combinatoires et Theorie des Graphes, eds. J.-C. Bermond, J.-C. Fournier, M. Las Vergnas, D. Sotteau, Editions du Centre National de la Recherche Scientifique, Paris, 1978, 441 | MR

[18] H. Sachs (ed.), “Graphs, hypergraphs and applications”, Proceedings of the Conference on Graph Theory (Eyba, GDR, 1984), B.G. Teubner Verlagsgesellschaft, Leipzig, 1985 | MR | Zbl

[19] R. Steinberg, “The state of the three color problem”, Quo vadis, graph theory?, Ann. Discrete Math., 55, eds. Gimbel John et al., 1993, 211–248 | DOI | MR | Zbl