There are no edge-chromatic 4-critical graphs of order 12 (Q1894759)

Let \(\chi'(G)\) and \(\Delta(G)\) denote respectively the chromatic index and the maximum degree of the vertices of a simple graph \(G\). Vizing's theorem says that \(\chi'(G)= \Delta(G)\) or \(\Delta(G)+ 1\). If \(\chi'(G)= \Delta(G)+ i- 1\), \(i= 1,2\), then \(G\) is said to be class \(i\). If \(G\) is a connected graph having \(\Delta(G)= \Delta\) and \(G\) is of class 2 such that \(\chi'(G- e)< \chi'(G)\) for any edge \(e\) of \(G\), then \(G\) is said to be \(\Delta\)-critical. Even order \(\Delta\)-critical graphs are rare. The smallest known 4-critical even order graph has 18 vertices. It has been proved that there are no 3-critical graphs of even order less than 16. In this paper the authors prove that there are no 4-critical graphs of order 12. This gives a partial answer to a question raised by the reviewer in the book [Some topics in graph theory (1986; Zbl 0588.05002)]. Misprint: In the proof of (R8), the edge \(e\) should be \(vw\).