## DIMACS TR: 97-39

## Chromatic-Index Critical Graphs of Even Order

### Authors: Stefan Grünewald and
Eckhard Steffen

**
ABSTRACT
**

A $k$-critrical graph $G$ has maximum degree $k \geq 0$,
chromatic index $\chi'(G) = k+1$ and $\chi'(G-e) < k+1$ for each
edge $e$ of $G$.

The Critical Graph Conjecture independently stated by I.T. Jakobsen
(On critical graphs with chromatic index 4, Disc. Math. 9 (1974) 265-276),
and
L. W. Beineke, R. J. Wilson (On the edge chromatic number of a graph,
Disc. Math. 5 (1973) 15-20) claims that every $k$-critical graph is of
odd order.
S. Fiorini, R. J. Wilson (Edge-colourings of graphs, in
L. W. Beineke, R. J. Wilson (eds.) Selected Topics in Graph Theory,
Academic Press London (1978) 103-126) conjectured that every
$k$-critical graph of even order has a 1-factor.
A. G. Chetwynd and H. P. Yap (Chromatic index critical graphs of order 9,
Disc. Math. 47 (1983) 23-33) stated the problem whether it is true that
if $G$ is a $k$-critical graph of odd order, then $G-v$ has a 1-factor
for every vertex $v$ of minimum degree.
These conjectures are disproved and the
problem is answered in the negative for $k \in \{3,4\}$.

We disprove these conjectures and answer the problem in the negative
for all $k \geq 3$.

We also construct $k$-critical graphs on $n$ vertices with degree
sequence $23^24^{n-3}$, answering a question of Yap (Some topics in
graph theory, London Math.~Soc.~LNS 108, Cambridge University Press (1986)).

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

DIMACS Home Page