Chromatic-index critical multigraphs of order 20
Stefan Grünewald · 2000
A multigraph M with maximum degree \\Delta(M ) is called critical, if the chromatic index Ø 0 (M) ? \\Delta(M ) and Ø 0 (M \\Gamma e) = Ø 0 (M) \\Gamma 1 for each edge e of M . The weak critical graph conjecture [1, 7] claims that there exists a constant c ? 0 such that every critical multigraph M with at most c \\Delta \\Delta(M ) vertices has odd order. We disprove this conjecture by constructing critical multigraphs of order 20 with maximum degree k for all k 5.