A generalization of Plantholt's theorem

Let K   2 n +1 ( r )denote the complete graph K 2 n +1 with each edge replicated r times and let χ′( G ) denote the chromatic index of a multigraph G. A multigraph G is critical if χ′( G ) > χ′( G/e ) for each edge e of G. Let S be a set of sn – 1 edges of K   2 n +1 ( r ) . We show that, for 0 < s ≦ r , G/S is critical and that χ′ ( G/(S ∪{ e })) = 2 rn + r – s for all e ∈ E ( G/S ). Plantholt [ M . Plantholt, The chromatic index of graphs with a spanning star. J. Graph Theory 5 (1981) 5–13] proved this result in the case when r = 1.