List supermodular coloring with shorter lists (Q2322511)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | List supermodular coloring with shorter lists |
scientific article |
Statements
List supermodular coloring with shorter lists (English)
0 references
4 September 2019
0 references
\textit{F. Galvin} [J. Comb. Theory, Ser. B 63, No. 1, 153--158 (1995; Zbl 0826.05026)] proved that a bipartite graph \(G\) admits a list edge coloring if every edge is assigned a color list of length \(\Delta(G)\), the maximum degree of the graph \(G\). This result was improved by \textit{O. V. Borodin} et al. [J. Comb. Theory, Ser. B 71, No. 2, 184--204 (1997; Zbl 0876.05032)], who proved that \(G\) still admits a list edge coloring if every edge \(st\) is assigned a list of \(\max\, \{\,d_G(s),\,d_G(t)\,\}\) colors. Recently, \textit{S. Iwata} and \textit{Y. Yokoi} [Combinatorica 38, No. 6, 1437--1456 (2018; Zbl 1424.05089)] provided the list supermodular coloring theorem that extends Galvin's result to the setting of Schrijver's supermodular coloring. In this work the author provides a common generalization of these two extensions of Galvin's result [loc. cit.].
0 references
bipartite graph
0 references
edge coloring
0 references
supermodular coloring
0 references