DIMACS TR: 97-59

Chromatic Index Critical Graphs of Orders 11 and 12

Authors: Gunnar Brinkmann and Eckhard Steffen


A chromatic-index-critical graph $G$ on $n$ vertices is non-trivial if it has at most $\Delta \lfloor \frac{n}{2} \rfloor$ edges.

We prove that there is no chromatic-index-critical graph of order 12, and that there are precisely two non-trivial chromatic index critical graphs on 11 vertices.

Together with known results this implies that there are precisely three non-trivial chromatic-index-critical graphs of order $\leq 12$.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-59.ps.gz

DIMACS Home Page