The chromatic index of multigraphs that are nearly full (Q910411)

A k-edge-colouring of a multigraph G is a mapping from the edge set of G onto a set of k colours such that no two adjacent edges are assigned the same colour. The chromatic index \(\chi'(G)\) of G is the minimum k for which a k-edge-colouring of G exists. In this paper known results concerning the estimation of the chromatic index of simple graphs are reviewed and generalizations of these results to multigraphs are proposed. The conjecture that, if S is any set of sn edges in \(K^{(r)}_{2n+1}\) \((K^{(r)}_{2n+1}\) denotes the regular multigraph obtained from \(K_{2n+1}\) by replacing each edge by r parallel edges), where \(r<s\leq 2r\), then \[ \chi'(K^{(r)}_{2n+1}-S)= \max\{\Delta(K^{(r)}_{2n+1}-S),\quad 2rn+r-s\} \] (\(\Delta(K^{(r)}_{2n+1}-S)\) denotes the maximum degree of \(K^{(r)}_{2n+1}-S)\), is proved for even r. The conjecture remains unproved for r odd, \(r>1\), but an upper bound of the chromatic index is given: \[ \chi'(K^{(r)}_{2n+1}-S)\leq 2+\max \{\Delta (K^{(r)}_{2n+1}-S),\quad 2rn+r-s\}. \]