A Hajós-like theorem for list coloring (Q1917503)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A Hajós-like theorem for list coloring |
scientific article; zbMATH DE number 897586
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A Hajós-like theorem for list coloring |
scientific article; zbMATH DE number 897586 |
Statements
A Hajós-like theorem for list coloring (English)
0 references
9 December 1996
0 references
\textit{G. Hajós} [Wiss. Z. Martin Luther Univ., Math.-Natur. Reihe 10, 116-117 (1961)] showed that every graph which is not \(q\)-colorable can be obtained from the complete graph \(K_{q + 1}\), by a sequence of operations of three types. The present author proves an analogue of this theorem for the list-chromatic number, applying again three operations (two of which agree with those of Hajós; the third is a variant), but now starting with a complete bipartite graph.
0 references
list coloring
0 references
list-chromatic number
0 references
0 references
0.9536952
0 references
0.9330493
0 references
0.9292114
0 references
0 references
0 references
0 references
