Aspects of edge list-colourings (Q5937593)
From MaRDI portal
scientific article; zbMATH DE number 1619844
Language | Label | Description | Also known as |
---|---|---|---|
English | Aspects of edge list-colourings |
scientific article; zbMATH DE number 1619844 |
Statements
Aspects of edge list-colourings (English)
0 references
28 November 2001
0 references
An assignment of colours to the edges of a multigraph is called an \(s\)-improper edge-colouring if no colour appears on more than \(s\) edges incident with any given vertex. In this paper it is proved that if \(L:E(G) \rightarrow 2^{N}\) is an assignment of lists of colours to the edges of a multigraph \(G\) with \(|L(e)|\geq \lceil \max {d(u),d(v)}/s\rceil \) for every edge \(e\) joining vertices \(u\) and \(v\), and either \(s\) is even or \(G\) is bipartite, then \(G\) has an \(s\)-improper \(L\)-edge-colouring in which no colour appears on too many parallel edges. The proof uses a new vertex-splitting lemma which generalizes the vertex-splitting lemma of the authors in [J. Comb. Theory, Ser. B 72, No.~1, 91-103 (1998; Zbl 0888.05030)]. Some applications of these results to school timetabling and conference scheduling are also presented.
0 references
list-colouring
0 references
multigraph
0 references
vertex-splitting lemma
0 references
chromatic index
0 references
\(s\)-improper edge-colouring
0 references