List supermodular coloring (Q2419323)

From MaRDI portal
scientific article
Language Label Description Also known as
English
List supermodular coloring
scientific article

    Statements

    List supermodular coloring (English)
    0 references
    0 references
    0 references
    12 June 2019
    0 references
    Galvin's theorem, see \textit{F. Galvin} [J. Comb. Theory, Ser. B 63, No. 1, 153--158 (1995; Zbl 0826.05026)] states that the list edge chromatic number of a bipartite graph is equal to the edge chromatic number of that graph. (The list colouring conjecture would be the same statement for all graphs, not necessarily bipartite). In the paper under review, the authors define a list colouring version of the so-called supermodular colourings from \textit{A. Schrijver} [Supermodular colourings, in: Matroid Theory, Proc. Colloq., Szeged/Hung. 1982, Colloq. Math. Soc. János Bolyai 40, 327--343 (1985; Zbl 0602.05018)] and show the analogous result that if there is a supermodular \(k\)-colouring for two intersecting supermodular functions, then there is also a list supermodular $k$-colouring. The proof uses a result of \textit{B. Sands} et al. [J. Comb. Theory, Ser. B 33, 271--275 (1982; Zbl 0488.05036)] on the existence of kernels in posets, and the notion of skeleton posets.
    0 references
    edge colouring
    0 references
    list colouring
    0 references
    Galvin's theorem
    0 references
    Gupta's theorem
    0 references
    supermodular colouring
    0 references

    Identifiers