List supermodular coloring with shorter lists (Q2322511)

From MaRDI portal
Revision as of 15:35, 14 September 2024 by Daniel (talk | contribs) (‎Created claim: Wikidata QID (P12): Q129793823, #quickstatements; #temporary_batch_1726323884171)
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