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