A vertex-splitting lemma, de Werra's theorem and improper list colourings
type: Item
instance of: scholarly article
title: A vertex-splitting lemma, de Werra's theorem and improper list colourings
zbMATH Open document ID: 0888.05030
author: D. S. G. Stirling
author: A. J. W. Hilton
author: T. Slivnik
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-09-15T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1060752
zbMATH Keywords: vertex-splitting lemma
zbMATH Keywords: multigraph
zbMATH Keywords: theorem of de Werra
zbMATH Keywords: list chromatic index
zbMATH Keywords: edge list colouring
zbMATH Keywords: colour
MaRDI profile type: Publication
full work available at URL: jctb.1997.1793
OpenAlex ID: W2009408226
cites work: Q3884118
cites work: The list chromatic index of a bipartite multigraph
cites work: Q4386303
cites work: Q5799732
cites work: Short Proof of Galvin's Theorem on the List-chromatic Index of a Bipartite Multigraph
cites work: Q4073396
cites work: On A Particular Conference Scheduling Problem
cites work: Q4135588
DOI: 10.1006/JCTB.1997.1793
description: scientific article; zbMATH DE number 1060752