The chromatic index of multigraphs of order at most 10 Original Research Article

The maximum of the maximum degree and the “odd set quotients” provides a well-known lower bound φ(G) for the chromatic index of a multigraph G. Plantholt proved that if G is a multigraph of order at most 8, its chromatic index equals φ(G) and that if G is a multigraph of order 10, the chromatic index of G cannot exceed φ(G) + 1. We identify those multigraphs G of order 9 and 10 whose chromatic index equals φ(G) + 1, thus completing the determination of the chromatic index of all multigraphs of order at most 10.