A new method of proving theorems on chromatic index

✍ Scribed by A. Ehrenfeucht; V. Faber; H.A. Kierstead

• Publisher: Elsevier Science
• Year: 1984
• Tongue: English
• Weight: 690 KB
• Volume: 52
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(84)90078-5

✦ Synopsis

V.G. Wing proved that the edge-chromatic 11umber x' of any multigraph M with m&mum degree A(M) aud maximum multiplicity p(M) is A(M)+pLM). In this paper we present a new

method for proving this and other related results that are due to Gol'dberg, Anderson, Ore, Shannon, and Vizing. In our proofs we replace arguments about 'fan sequences' with counting arguments.

1. Ilhtmduction

V.G. Vking [6] proved that the edge-chromatic number ,x' of any multigraph M with maximum degree A(M) and maximum multiplicity &f) is A(M)+ p(M). In this paper we present a new method for proving this and other related results that are due to Gol'dberg [3], Anderson Cl]:. Ore [4], Shannon [S], and Vizing [7]. In our proofs we replace arguments about 'fan sequences' ti& counting arguments. The main ideas are contained in Lemma I, from which we (can immediately derive the theorems of Shannon, Vizing and Ore. After proving these basic results, we strengthen the proof of Lemma 1 in two different ways to, derive more technical results of Gol'dberg, Anderson and Vi&g. The results of this paper wert: announmd in @]. l%t~&n. Let M = (V, E) be a multigraph. We denote the set of edges between vertices 2) and w by uw and luw! by I. Also, p(u) denotes nxq,,,v I, N(O) denote3 the set of vertices adjacent tc the vertex u, I(u) denotes the set of edges incident with o, and S(u) C&(u)] denotes II(u). Finally, let f be a partial edge-coloring of a multigraph M. For each pair of vertices u and w, I is the set of colors (in the range of ,d) that are not used on