A vertex-splitting lemma, de Werra's theorem and improper list colourings (Q1366607)

We prove the new vertex-splitting lemma that if a multigraph \(G\) has maximum multiplicity at most \(p\) then each vertex \(u\) can be split into \(\lceil\frac {d(u)}{p}\rceil\) new vertices, \(\lfloor\frac {d(u)}{p}\rfloor\) of degree \(p\), and the multiple edges 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-coloring for each positive integer \(k\). We also apply the lemma to improve two earlier theorems of the first author that \(\chi_s^{\prime\ell}(G)= \lceil\frac {\Delta(G)} {s}\rceil\) if either \(G\) is a bipartite multigraph, or \(s\) is even and \(G\) is any multigraph; here \(\chi_s^{\prime\ell} (G)\) is the \(s\)-improver 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 \(\ell(e)\) of at least \(k\) colours, then \(G\) has an \(s\)-improper edge list colouring (so that at each vertex \(v\) not more than \(s\) edges incident with \(v\) 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,v)\), no colour is used on more than \(\lceil m_G(u,v)/ \lceil\frac {\Delta(G)} {s}\rceil\rceil+1\) edges joining \(u\) and \(v\).