Chromatic-index-critical graphs of orders 11 and 12 (Q1277310)

A simple graph \(G\) with maximum vertex degree \(\Delta\) is called \(\Delta\)-critical (or chromatic-index-critical) if the chromatic index \(\chi'(G)\) of \(G\) is \(\Delta+1\) and \(\chi'(G-e)=\Delta\) for any edge \(e\) of \(G\). A \(\Delta\)-critical graph \(G=(V,E)\) having at most \(\Delta\left\lfloor{| V|\over 2}\right\rfloor\) edges is said to be non-trivial. \textit{L. W. Beineke} and \textit{S. Fiorini} [Discrete Math. 16, 109-121 (1976; Zbl 0344.05121)] proved that there are no chromatic-index-critical graphs of even order at most 10. In this paper it is shown that there are no chromatic-index-critical graphs of order 12. (A shorter proof that there are no chromatic-index-critical graphs of order 10 is given in a forthcoming paper by Z. X. Song and the reviewer.) It was known that the graph obtained by deleting any vertex from the Petersen graph is the only non-trivial odd order chromatic-index-critical graph of order at most 10. The authors, using computers, show that there are precisely two non-trivial chromatic-index-critical graphs of order 11. The previous known results together with the new results proved in this paper imply that there are precisely three non-trivial chromatic-index-critical graphs of order at most 12.