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/