×

zbMATH — the first resource for mathematics

List supermodular coloring with shorter lists. (English) Zbl 1438.05108
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 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, S. Iwata and 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.].
MSC:
05C15 Coloring of graphs and hypergraphs
68R05 Combinatorics in computer science
PDF BibTeX XML Cite
Full Text: DOI arXiv