View PDF HTML (experimental)

Abstract:A graph $G$ with maximum degree $\Delta$ is $\Delta$-critical if it is connected, satisfies $\chi'(G)=\Delta+1$, and the deletion of any edge reduces its chromatic index to $\Delta$. A $\Delta$-critical graph $G$ is called nontrivial if it contains no $\Delta$-overfull subgraph; that is, no $H \subseteq G$ such that $|E(H)| > \Delta \lfloor |V(H)| /2 \rfloor$. There are no $1$-critical graphs, and the $2$-critical graphs are exactly the odd cycles. By work of Chetwynd and Yap from 1983, there is a unique nontrivial $3$-critical graph of order $9$, and exactly two nontrivial $3$-critical graphs of order $11$. In 2005, Bokal, Brinkmann, and Grünewald showed that there are exactly fourteen nontrivial $3$-critical graphs of order $13$. For even orders, Brinkmann and Steffen proved in 1997 that no $3$-critical graphs of even order exist below order $22$, there is exactly one 3-critical graph of order $22$, and that there are exactly nine $3$-critical graphs of order $24$.
To the best of our knowledge, there has been no further progress on the existence of nontrivial $3$-critical graphs of odd orders beyond the cases established two decades ago. In this paper, using computer-assisted search techniques, we determine the exact numbers of nontrivial $3$-critical graphs of odd orders from $15$ to $21$. The same data pipeline also reproduces the known order-$22$ count of Brinkmann and Steffen, with one nontrivial $3$-critical graph. Beyond enumeration, we prove a characterization theorem for all nontrivial 3-critical graphs, with one case based on snarks. We also provide an analysis of our search algorithm.

Submission history

From: Songling Shan [view email]
[v1] Thu, 25 Jun 2026 15:08:48 UTC (34 KB)