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
    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

    Identifiers