A Vertex-Splitting Lemma, de Werra's Theorem, and Improper List Colourings
✍ Scribed by A.J.W. Hilton; D.S.G. Stirling; T. Slivnik
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 418 KB
- Volume
- 72
- Category
- Article
- ISSN
- 0095-8956
No coin nor oath required. For personal study only.
✦ Synopsis
We prove a new vertex-splitting lemma which states that if a multigraph G has maximum multiplicity of at most p, then each vertex u can be split into W(d(u)Âp)X new vertices, w(d(u)Âp)x of degree p, with the multiple edges being shared out between the new vertices in such a way that each multiple edge remains intact at at least one of its two endpoints. We apply this lemma to deduce very simply the theorem of de Werra that each bipartite multigraph has a balanced k-edge-colouring for each positive integer k.
We also apply the lemma to improve two earlier theorems of the first author which state that /$ l s (G)=W(2(G)Âs)X if either (1) G is a bipartite multigraph, or (2) s is even and G is any multigraph; here /$ l s (G) is the s-improper list chromatic index of G, i.e., the least possible value of k such that, if each edge of G is provided with a list l(e) of at least k colours, then G has an s-improper edge list colouring (so that at each vertex & not more than s edges incident with & receive the same colour), and, on each edge, the colour used lies in the list for that edge. The improvements that we obtain include that for each multiple edge of multiplicity m=m G (u, &), no colour is used on more than Wm G (u, &)Â W(2(G)Âs)X X+1 edges joining u and &.
1998 Academic Press
1. Introduction
In this paper we give a vertex-splitting result which is new and elementary. This result is then applied to give a simple proof of a well-known theorem of de Werra [6 8] and to improve two recent results of the first author concerning edge-list colourings. For another proof of de Werra's theorem, see [1].