RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2023 Volume 20, Issue 2, Pages 847–853 (Mi semr1614)

Discrete mathematics and mathematical cybernetics

Edge $4$-critical Koester graph of order $28$

A. A. Dobrynin

Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia

Abstract: 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.

UDC: 519.17

MSC: 05C15

Received June 3, 2023, published October 26, 2023

Language: English

DOI: 10.33048/semi.2023.20.051



© Steklov Math. Inst. of RAS, 2025