## DIMACS TR: 97-59

## Chromatic Index Critical Graphs of Orders 11 and 12

### Authors: Gunnar Brinkmann and Eckhard Steffen

**
ABSTRACT
**

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