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