\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}

\def\udcs{519.17} %Здесь автор определяет УДК своей работы
\def\mscs{05C15} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{144}

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{problem}{Problem}

\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\semrtop
     {
  \vbox{
     \noindent\logo
     \hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }

     \vspace{5mm}

     \begin{center}
     {\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]
     {\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
     {\large Siberian Electronic Mathematical Reports} \\[1mm]
     {\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
     \vspace{-3mm}
     \noindent
     \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
     \hline\hline
     \end{tabular}

     \vspace{1mm}
     {\flushleft\it Том 20, стр. 144--144 (2023) \hspace{63mm}{\rm\small УДК \udcs}}
     \newline
     	{\rm\small DOI~10.33048/semi.2019.16.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaai}{\rm\small MSC\  \mscs }
  }%\vbox
}

\begin{document}
\renewcommand{\refname}{References}
\renewcommand{\figurename}{Fig.}
\renewcommand{\tablename}{Table}
\renewcommand{\proofname}{Proof.}

\thispagestyle{empty}

\title[Edge 4-critical Koester graph of order 28]{Edge 4-critical Koester graph of order 28}
\author{{A.A. DOBRYNIN}}%
\address{Andrey Alekseevich Dobrynin  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} pr. Koptyuga, 4,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{dobr@math.nsc.ru}%

\thanks{\sc Dobrynin, A.A.,
Edge 4-critical Koester graph of order 28}
\thanks{\copyright \ 2023 Dobrynin A.A}
\thanks{\rm The study was carried out within the framework of the state contract
of the Sobolev Institute of Mathematics (project number FWNF-2022-0017).}
\thanks{\it Received June, 3, 2023, published xxxxx xx, 202x}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc 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.\medskip

\noindent{\bf Keywords:} plane graph, 4-critical graph, Gr\"{o}tzsch--Sachs graph, Koester graph.
 \end{quote}
}

\section{Introduction}

In this paper we are concerned with simple undirected connected graphs.
A graph is $k$-\textit{chromatic} if its chromatic number is equal to $k$.
A graph is called \textit{edge 4-critical} if it is
4-chromatic and the removal
of any edge decreases its chromatic number.
Numerous results and problems related to critical graphs can be found in
\cite{BeWi15,JT95}.
Consider a graph $G=G(S)$ formed by the superposition of a set $S$ of
circles in the plane, no two of which are tangent and no three
circles share a point. Crossing points and arcs of the set $S$
correspond to vertices and edges of $G$, respectively.
Since any two circles of $S$ either do not intersect or
have exactly two crossing points,
$G$ is always a 4-regular plane graph of even order.
Such regular graphs are called \textit{Koester graphs}.
To describe the mutual position of circles of $S$,
we use the \textit{characteristic graph} $H(S)$.
It is the intersection graph of the circles:
vertices of $H(S)$ correspond to members of $S$ and two vertices are adjacent
if and only if the corresponding circles intersect.
We use notation $H(G)$ if a graph $G$ is generated by $S$.
Koester graphs are a special case of \textit{Gr\"{o}tzsch--Sachs graphs}
which are formed by intersections of closed curves in the plane.
The first studies concerning coloring of such graphs are due to H.~Gr\"{o}tzsch.
H.~Sachs actively discussed the problems arising in this area at conferences.
We briefly describe some results on the coloring of Gr\"{o}tzsch--Sachs graphs
(see \cite{S84,Ja76,Ja78,JaSa,K84,K85a,K85b,S74,S78a,St93,DoMel12}).
F.~Jaeger proved that $\chi(G)\leq 3$ if $\chi(H(G))\leq 3$
 \cite{Ja76,Ja78}.
Examples and infinite families of 4-chromatic or
edge 4-critical Gr\"{o}tzsch--Sachs graphs were presented in
\cite{Chiu22,DoMel06,DoMelFull,DoMelSub,DoMel09,DoMel12}.
In particular, Gr\"{o}tzsch--Sachs--Koester's conjecture
stating that if $\chi(H(G))=4$ then $\chi(G) \leq 3$ was disproved
by constructing counterexamples on 18 vertices
\cite{DoMel06}.
In 1984, G.~Koester found the first example of an edge 4-critical
Gr\"{o}tzsch--Sachs graph
(see graph $K^1$  in Fig.~\ref{Fig1}).
Graph $K^1$ of order 40 is generated by a set of seven circles
and its characteristic graph is $K_7 - e$
\cite{K84,K85a,K85b}.
It was the only example of graphs of this kind for a long time.
A new edge 4-critical Koester graph $K^2$
can be obtained by rearranging circles of $K^1$ as shown in Fig.~\ref{Fig1}
\cite{Dobr23}.
Since  $H(K^2) \cong K_7 - e$, graph $K^2$ also has 40 vertices.
In this paper, an edge 4-critical Koester graph of order 28 formed by six circles
in the plain is presented.
This gives a new upper bound for the smallest order of such graphs.

\begin{figure}[t]
\centering
\includegraphics[width=0.75\linewidth]{Fig1.eps}
\caption{Edge 4-critical Koester graphs of order 40.}
\label{Fig1}
\end{figure}

\section{Construction of a graph}

Let $K$ be a 4-regular graph  of order 28
generated by six circles in the plane as shown in
Fig.~\ref{Fig2}.
Since the circle set has the unique pair of non-crossing circles,
the characteristic graph of $K$ is $K_6-e$.
The circles correspond to two cycles of order 8 and four cycles of order 10
of $K$:
disjoint red cycles
$R_1 =  (14, 16, 27, 21, 19, 8, 1, 5)$ and
$R_2  =  (11, 15, 26, 25, 24, 10, 2, 3)$,
blue cycle
$M = (4, 14, 18, 20, 21, 23, 22, 10, 9, 3)$,
black cycle
$B = (4, 11, 13, 26, 28, 23, 19, 7, 6, 5)$,
green cycle
$G = (1, 2, 9, 12, 25, 28, 27,$ $20, 17, 6)$,
and orange cycle
$O = (15, 16, 18, 17, 7, 8, 22, 24, 12, 13)$.

The automorphism group of $K$ has order 2 and contains an involution that maps
cycles $R_1$ and $R_2$ into itself, cycle $B$ to cycle $M$,
and cycle $G$ to cycle $O$.
Vertices 4,  23, 12, and 17 are fixed by the involution and
the other vertices form twelve two-element orbits:
(5,14), (1,16),  (8,27), (19,21),
(3,11), (2,15), (10,26), (24,25),
(6,18),  (7,20), (9,13), and (22,28).
Four of the above orbits are edges of $K$,
namely, $(5,14)$, $(19,21)$ in $R_1$ and $(3,11)$, $(24,25)$ in $R_2$.

\begin{figure}[t]
\centering
\includegraphics[width=0.6\linewidth]{Fig2.eps}
\caption{Edge 4-critical Koester graph $K$ of order 28.}
\label{Fig2}
\end{figure}

\begin{proposition}
Koester graph $K$ is 4-chromatic.
\end{proposition}
\proof
The presence of odd cycles in $K$ implies $\chi(K) \ge 3$.
Since $K$ is a 4-regular graph, $\chi(K) \le 4$ by Brooks' theorem.
Suppose that $K$ is a 3-chromatic graph and try to find a 3-coloring of $K$.
First, we color vertices of some pentagonal face (5-face) in all possible ways.
Further we show that it is impossible to extend any coloring of this face
to the entire graph $K$.
Take face $f_5=(17,18,14,5,6)$ for the initial coloring
(see Fig.~\ref{Fig2}).
The colored vertices of the graph will be drawn as red, white and green circles.
We need exactly 3 colors for vertices of a 5-face in
a 3-chromatic graph.
Color of one vertex of a 5-face always distinct from colors of the other
vertices of the face. Let this unique color be red.
The following two useful rules will be applied
in the process of graph coloring.

1. Let a graph $G$ be obtained from the simple path of order 4 by joining a new vertex
with non-pendant vertices of the path.
Suppose that pendant vertices of $G$ have the same color in
a proper 3-coloring. Then the vertex of degree two of $G$
must have this color.

2. Let $G$ consists of two triangles having one common edge.
Then two vertices of degree 2 of $G$ must have the same color in
a proper 3-coloring of $G$.

All possible extensions of the colorings of the
initial face $f_5$ are shown in
Fig.~\ref{Fig3}.
Every uncolored vertex gets a forced color at some step of the coloring procedure.
The numbers of steps are depicted near graph vertices.
The question mark shows an edge whose vertices cannot be properly colored.
If a vertex color is determined, say, in step 6 by the vertex colors
obtained at steps 2 and 5, we use record $s(2,5) \rightarrow s(6)$.
The number of the applied coloring rule will be indicated as a subscript of $s$.
We will draw in gray the edges that are not used in finding 3-colorings.
The initial 5-face can be colored by five cases.
In accordance with the initial coloring of face $f_5$, we consider five cases.

Case A. Let vertex 17 of face $f_5$ be red
(see Fig.~\ref{Fig3}a).
The following sequence of coloring steps uniquely defines colors
of some vertices of graph $K$:
$s(1,2) \rightarrow s(7)$,
$s(2,3) \rightarrow s(8)$,
$s(4,5) \rightarrow s(9)$,
$s(7,8) \rightarrow s(10)$,
$s(7,10) \rightarrow s(11)$,
$s(6,11) \rightarrow s(12)$, and
$s(6,12) \rightarrow s(13)$.
Since the end-vertices of edge (1,8) have the same color,
we cannot get a proper 3-coloring of graph $K$ .

\begin{figure}[t]
\centering
\includegraphics[width=\linewidth]{Fig3.eps}
\caption{Steps of 3-colorings of graph $K$.}
\label{Fig3}
\end{figure}

Case B. Let vertex 18 of face $f_5$ be red
(see Fig.~\ref{Fig3}b).
Then
$s(4,5) \rightarrow s(6)$,
$s(1,5) \rightarrow s(7)$,
$s(1,2) \rightarrow s(8)$,
$s(2,3) \rightarrow s(9)$,
$s(3,4) \rightarrow s(10)$,
$s(7,8) \rightarrow s(11)$,
$s_1(6,11) \rightarrow s(12)$,
$s_1(9,10) \rightarrow s(13)$,
$s_1(12,13) \rightarrow s(14)$,
$s_1(12,14) \rightarrow s(15)$, and
$s_2(15) \rightarrow s(16)$.
As a result of this partial 3-coloring, edge (4,11)
has end-vertices with the same color.

Case C. Let vertex 14 of face $f_5$ be red
(see Fig.~\ref{Fig3}c).
We have
$s(4,5) \rightarrow s(6)$,
$s(3,4) \rightarrow s(7)$,
$s(1,5) \rightarrow s(8)$,
$s(6,8) \rightarrow s(9)$,
$s(6,9) \rightarrow s(10)$,
$s(7,10) \rightarrow s(11)$,
$s(10,11) \rightarrow s(12)$,
$s(9,12) \rightarrow s(13)$,
$s_1(8,13) \rightarrow s(14)$,
$s_1(2,14) \rightarrow s(15)$,
$s_2(15) \rightarrow s(16)$, and
$s_1(14,16) \rightarrow s(17)$.
End-vertices of edge (25,28) cannot be colored properly.

Case D. Let vertex 5 of face $f_5$ be red
(see Fig.~\ref{Fig3}d).
Then
$s(1,2) \rightarrow s(6)$,
$s(2,3) \rightarrow s(7)$,
$s(3,4) \rightarrow s(8)$,
$s(6,7) \rightarrow s(9)$,
$s_1(7,8) \rightarrow s(10)$,
$s(9,10) \rightarrow s(11)$,
$s_1(6,11) \rightarrow s(12)$,
$s_1(5,12) \rightarrow s(13)$,
$s_2(13) \rightarrow s(14)$, and
$s_1(11,14) \rightarrow s(15)$.
End-vertices of edge (9,12) have the same colors.

Case E. Let vertex 6 of face $f_5$ be red
(see Fig.~\ref{Fig3}e).
Then
$s(1,2) \rightarrow s(6)$,
$s(2,3) \rightarrow s(7)$,
$s(3,4) \rightarrow s(8)$,
$s(4,5) \rightarrow s(9)$,
$s(1,5) \rightarrow s(10)$,
$s(6,10) \rightarrow s(11)$,
$s_1(7,11) \rightarrow s(12)$,
$s_1(8,9) \rightarrow s(13)$,
$s_1(12,13) \rightarrow s(14)$,
$s_1(11,14) \rightarrow s(15)$, and
$s_2(15) \rightarrow s(16)$.
Vertices of edge (3,4) are colored in the same color.

The considered cases lead to the impossibility of 3-coloring of graph $K$ and,
therefore, $K$ is a 4-chromatic graph.
\endproof

\begin{proposition}
Koester graph $K$ is edge critical.
\end{proposition}
\proof
To prove that every edge of $K$ is critical, we present a 3-coloring of graph $K-e$
for every edge $e$ of $K$. Because of symmetry of $K$, it is sufficient
to consider 30 edges.
Since the involution fixes two edges of cycles $R_1$ and $R_2$ of length 8,
we should check 5 edges from every cycle.
Then we check all edges from cycles $M$ and $O$ of length 10.
Vertex colorings of $K-e$ for these edges $e$ are presented in Table~\ref{Tab1}.
The header of Table~\ref{Tab1} contains the vertex numbering of $K$.
The colors of vertices are located in the columns of the table.
As an illustration, a 3-coloring of graph $K-(15,16)$ is depicted in Fig.~\ref{Fig4}
\endproof

\begin{figure}[b]
\centering
\includegraphics[width=0.5\linewidth]{Fig4.eps}
\caption{3-coloring of graph $K-(15,16)$.}
\label{Fig4}
\end{figure}

The order of the constructed graph $K$ improves an upper bound
for the smallest order of edge 4-critical Koester graphs.
Computer search shows that there are no such graphs with the number of vertices
less than 22.
It would be interesting to answer to the following question:
does there exist an edge 4-critical Koester graph of order 22, 24, or 26?

\begin{table}[t]
\caption{3-colorings of graph $K$.}
\label{Tab1}
\resizebox{\textwidth}{!}{
\begin{tabular}{c@{\hspace{0.5mm}}c@{\hspace{2mm}}r@{\hspace{2mm}}r@{\hspace{2mm}}r@{\hspace{2mm}}r@{\hspace{2mm}}
r@{\hspace{2mm}}r@{\hspace{2mm}}r@{\hspace{2mm}}r@{\hspace{2mm}}r@{\hspace{1mm}}r@{\hspace{1mm}}
r@{\hspace{1mm}}r@{\hspace{1mm}}r@{\hspace{1mm}}r@{\hspace{1mm}}r@{\hspace{1mm}}r@{\hspace{1mm}}
r@{\hspace{1mm}}r@{\hspace{1mm}}r@{\hspace{1mm}}r@{\hspace{1mm}}r@{\hspace{1mm}}r@{\hspace{1mm}}
r@{\hspace{1mm}}r@{\hspace{1mm}}r@{\hspace{1mm}}r@{\hspace{1mm}}r@{\hspace{1mm}}r@{\hspace{1mm}}r} \hline
$N$ & $e$  & 1  & 2 & 3& 4&5 & 6& 7& 8&9 & 10 &11 & 12 &13 &14 &15 &16 &17 &18 &19
           &20 &21 &22 &23 &24 &25 &26 &27&28 \\
\hline
1 & ( 1, 5)  &1 &2 &1 &3 &1 &2 &1 &3 &3 &1 &2 &2 &3 &2 &1 &3 &3 &1 &2 &2 &3 &2 &1 &3 &1 &2 &1 &3 \\
2 & ( 1, 8)  &1 &2 &1 &3 &2 &3 &2 &1 &3 &1 &2 &2 &3 &1 &1 &3 &1 &2 &3 &3 &2 &2 &1 &3 &1 &2 &1 &3 \\
3 & ( 2, 3)  &1 &2 &2 &3 &2 &3 &1 &2 &3 &1 &1 &1 &2 &1 &3 &2 &2 &3 &3 &1 &2 &3 &1 &2 &3 &1 &3 &2 \\
4 & ( 2,10)  &1 &2 &1 &2 &3 &2 &3 &2 &3 &2 &3 &2 &1 &1 &2 &3 &1 &2 &1 &3 &2 &1 &3 &3 &1 &3 &1 &2 \\
5 & ( 3, 4)  &1 &2 &1 &1 &3 &2 &1 &3 &3 &1 &2 &2 &3 &2 &1 &3 &3 &1 &2 &2 &3 &2 &1 &3 &1 &2 &1 &3 \\
6 & ( 3, 9)  &1 &2 &1 &2 &3 &2 &3 &2 &1 &3 &3 &3 &2 &1 &1 &3 &1 &2 &1 &3 &2 &1 &3 &2 &1 &3 &1 &2 \\
7 & ( 3,11)  &1 &2 &1 &3 &2 &3 &1 &2 &3 &1 &1 &1 &2 &1 &3 &2 &2 &3 &3 &1 &2 &3 &1 &2 &3 &1 &3 &2 \\
8 & ( 4,14)  &1 &2 &1 &2 &3 &2 &1 &3 &3 &1 &3 &2 &1 &2 &2 &3 &3 &1 &2 &2 &3 &2 &1 &3 &1 &3 &1 &2 \\
9 & ( 5,14)  &1 &2 &1 &3 &2 &3 &1 &2 &3 &1 &2 &1 &3 &2 &1 &3 &2 &1 &3 &3 &1 &3 &2 &2 &3 &2 &2 &1 \\
10 & ( 7, 8)  &1 &2 &1 &3 &2 &3 &2 &2 &3 &1 &2 &1 &3 &1 &1 &2 &1 &3 &3 &2 &1 &3 &2 &2 &3 &2 &3 &1 \\
11 & ( 7,17)  &1 &2 &1 &3 &2 &3 &1 &3 &3 &1 &2 &2 &3 &1 &1 &2 &1 &3 &2 &2 &3 &2 &1 &3 &1 &2 &1 &3 \\
12 & ( 8,19)  &1 &2 &1 &3 &2 &3 &2 &3 &3 &1 &2 &2 &3 &1 &1 &3 &1 &2 &3 &3 &2 &2 &1 &3 &1 &2 &1 &3 \\
13 & ( 8,22)  &1 &2 &1 &2 &3 &2 &3 &2 &3 &1 &3 &2 &1 &1 &2 &3 &1 &2 &1 &3 &2 &2 &3 &3 &1 &3 &1 &2 \\
14 & ( 9,10)  &1 &2 &3 &1 &3 &2 &1 &3 &1 &1 &2 &2 &3 &2 &1 &3 &3 &1 &2 &2 &3 &2 &1 &3 &1 &2 &1 &3 \\
15 & (10,22)  &1 &2 &1 &3 &2 &3 &2 &3 &3 &1 &2 &2 &3 &1 &1 &2 &1 &3 &1 &2 &3 &1 &2 &3 &1 &2 &1 &3 \\
16 & (10,24)  &1 &2 &3 &1 &3 &2 &1 &3 &1 &3 &2 &2 &3 &2 &1 &3 &3 &1 &2 &2 &3 &2 &1 &3 &1 &2 &1 &3 \\
17 & (12,13)  &1 &2 &3 &2 &3 &2 &1 &3 &1 &3 &1 &3 &3 &1 &2 &3 &3 &2 &2 &1 &3 &2 &1 &1 &2 &1 &2 &3 \\
18 & (12,24)  &1 &2 &3 &2 &3 &2 &3 &2 &1 &3 &1 &2 &3 &1 &2 &3 &1 &2 &1 &3 &2 &1 &3 &2 &3 &1 &1 &2 \\
19 & (13,15)  &1 &2 &1 &3 &2 &3 &2 &3 &3 &1 &2 &2 &1 &1 &1 &3 &1 &2 &1 &3 &2 &2 &3 &3 &1 &3 &1 &2 \\
20 & (14,18)  &1 &2 &1 &3 &2 &3 &1 &2 &3 &1 &2 &1 &3 &1 &1 &3 &2 &1 &3 &3 &1 &3 &2 &2 &3 &2 &2 &1 \\
21 & (15,16)  &1 &2 &3 &2 &3 &2 &1 &3 &1 &3 &1 &3 &2 &1 &3 &3 &3 &2 &2 &1 &3 &2 &1 &1 &2 &1 &2 &3 \\
22 & (16,18)  &1 &2 &1 &3 &2 &3 &1 &3 &3 &1 &2 &2 &3 &1 &1 &3 &2 &3 &2 &1 &3 &2 &1 &3 &1 &2 &2 &3 \\
23 & (17,18)  &1 &2 &1 &3 &2 &3 &1 &3 &3 &1 &2 &2 &3 &1 &1 &3 &2 &2 &2 &1 &3 &2 &1 &3 &1 &2 &2 &3 \\
24 & (18,20)  &1 &2 &1 &2 &3 &2 &1 &3 &3 &1 &3 &2 &1 &1 &2 &3 &3 &2 &2 &2 &3 &2 &1 &3 &1 &3 &1 &2 \\
25 & (19,21)  &1 &2 &3 &1 &2 &3 &2 &3 &1 &3 &2 &3 &1 &3 &3 &1 &1 &2 &1 &3 &1 &1 &2 &2 &1 &2 &2 &3 \\
26 & (20,21)  &1 &2 &1 &3 &2 &3 &1 &2 &3 &1 &2 &1 &3 &1 &1 &2 &2 &3 &3 &1 &1 &3 &2 &2 &3 &2 &3 &1 \\
27 & (21,23)  &1 &2 &1 &3 &2 &3 &1 &2 &3 &1 &2 &1 &3 &1 &1 &2 &2 &3 &3 &1 &2 &3 &2 &2 &3 &2 &3 &1 \\
28 & (22,23)  &1 &2 &1 &3 &2 &3 &2 &3 &3 &1 &2 &2 &3 &1 &1 &2 &1 &3 &1 &2 &3 &2 &2 &3 &1 &2 &1 &3 \\
29 & (22,24)  &1 &2 &3 &2 &3 &2 &3 &2 &1 &3 &1 &2 &3 &1 &2 &3 &1 &2 &1 &3 &2 &1 &3 &1 &3 &1 &1 &2 \\
30 & (24,25)  &1 &2 &3 &2 &3 &2 &3 &2 &1 &3 &1 &3 &2 &1 &3 &2 &1 &3 &1 &2 &3 &1 &2 &2 &2 &1 &1 &3 \\
\hline
\end{tabular}
 }
\end{table}


\section*{Acknowledgments}

The author is grateful to the referee for useful suggestions.


\bigskip
\begin{thebibliography}{99}
\bibitem{BeWi15}
L.~Beineke, R.~Wilson~(Eds.),
{\it Topics in Chromatic Graph Theory.}
Encyclopedia of Mathematics and its Applications.
Cambridge University Press, Cambridge, 2015.

\bibitem{Chiu22}
M.-K.~Chiu, S.~Felsner, M.~Scheucher, F.~Schr\"{o}der, R.~Steiner, B.~Vogtenhuber,
{\it Coloring circle arrangements: New 4-chromatic planar graphs},
arXiv:2205.08181v1.
https://doi.org/10.48550/arXiv.2205.08181 (2022)

\bibitem{Dobr23}
A.A.~Dobrynin,
{\it A new 4-chromatic edge critical Koester graph},
Discrete Math. Lett.,
\textbf{12} (2023), 6--10.
https://doi.org/10.47443/dml.2022.166

\bibitem{DoMel06}
A.A.~Dobrynin, L.S.~Mel'nikov,
{\it Counterexamples to Gr\"{o}tzsch--Sachs--Koester's conjecture},
Discrete Math.,
\textbf{306} (2006), 591--594.
https://doi.org/10.1016/j.disc.2005.08.010

\bibitem{DoMelFull}
A.A.~Dobrynin, L.S.~Mel'nikov,
{\it Two series of edge 4--critical Gr\"{o}tzsch--Sachs graphs generated by four curves in the plane},
Siberian Electron. Math. Rep.,
\textbf{5} (2008), 255--278.

\bibitem{DoMelSub}
A.A.~Dobrynin, L.S.~Mel'nikov,
{\it Infinite families of 4--chromatic Gr\"{o}tzsch--Sachs graphs},
J.~Graph Theory,
\textbf{59}:4 (2008), 279--292.
https://doi.org/10.1002/jgt.20339

\bibitem{DoMel09}
A.A.~Dobrynin, L.S.~Mel'nikov,
{\it 4--chromatic edge critical Gr\"{o}tzsch--Sachs graphs},
Discrete Math.,
\textbf{309}:8 (2009), 2564--2566.
https://doi.org/10.1016/j.disc.2008.06.006

\bibitem{DoMel12}
A.A.~Dobrynin, L.S.~Mel'nikov,
{\it 4-chromatic Koester graphs},
Discuss. Math. Graph Theory,
\textbf{32}:4 (2012), 617--627.
https://doi.org/10.7151/dmgt.1630

\bibitem{Ja76}
F.~Jaeger,
{\it On nowhere-zero flows in multigraphs},
in: C.St.J.A.~Nash-Williams, J.~Sheehan (Eds.),
Proc. Fifth British Combinatorial Conference 1975,
Congressus Numerantium XV, pp. 682--683,
Utilitas Mathematica Pub., Winnipeg, 1976.

\bibitem{Ja78}
F.~Jaeger,
{\it Sur les graphes couverts par leurs bicycles et la conjecture des quatre couleurs},
in: ~J.-C.~Bermond, J.-C.~Fournier, M.~Las~Vergnas, D.~Sotteau (Eds.),
{\it Probl\`{e}mes Combinatoires et Theorie des Graphes}, pp. 243--247,
Editions du Centre National de la Recherche Scientifique, Paris,
1978.

\bibitem{JaSa}
F.~Jaeger, H.~Sachs,
{\it Problems}.
in: L.D.~Andersen, I.T.~Jakobsen, C.~Thomassen, B.~Toft, P.D.~Vestergaard (Eds.),
{\it Graph Theory in Memory of G.A.~Dirac.}, Ann. Discrete Math. \textbf{41},
1989, p. 515.
https://doi.org/10.1016/S0167-5060(08)70487-4

\bibitem{JT95}
T.~Jensen, B.~Toft,
{\it Graph Coloring Problems},
John Wiley \& Sons, New York,
1995.

\bibitem{K84}
G.~Koester,
{\it Bemerkung zu einem Problem von H.~Gr\" otzsch},
Wiss. Z. Univ. Halle,
\textbf{33} (1984), 129.

\bibitem{K85a}
G.~Koester,
{\it Coloring problems on a class of 4--regular planar graphs},
in: H.~Sachs (Ed.), {\it Graphs, Hypergraphs and Applications},
Proc. Conference on Graph Theory, Eyba, 1984,
B.G. Teubner Verlagsgesellschaft,
1985, pp. 102--105.

\bibitem{K85b}
G.~Koester,
{\it Note to a problem of T.~Gallai and G.A.~Dirac},
Combinatorica,
\textbf{5} (1985), 227--228.
https://doi.org/10.1007/BF02579365

\bibitem{S74}
H.~Sachs,
{\it Problem}.
Math. Balkanica,
\textbf{4} (1974), 536.

\bibitem{S78a}
H.~Sachs,
{\it A Three--Colour--Conjecture of Gr\"{o}tzsch},
in: J.-C.~Bermond, J.-C.~Fournier, M.~Las~Vergnas, D.~Sotteau (Eds.),
{\it Probl\`{e}mes Combinatoires et Theorie des Graphes}, p.~441,
Editions du Centre National de la Recherche Scientifique, Paris,
1978.

\bibitem{S84}
H.~Sachs (Ed.),
{\it Graphs, Hypergraphs and Applications}.
Proc. Conference on Graph Theory, Eyba, 1984.
B.G. Teubner Verlagsgesellschaft, 1985.

\bibitem{St93}
R.~Steinberg,
{\it The state of the three color problem}.
in: J.~Gimbel, J.W.~Kennedy, L.V.~Quintas (Eds.),
{\it Quo Vadis, Graph Theory?}, Annals Discrete Math.
\textbf{55}, 1993, pp. 211--248.
https://doi.org/10.1016/S0167-5060(08)70391-1
\end{thebibliography}

\end{document}


