zbMATH — the first resource for mathematics

A Hajós-like theorem for list coloring. (English) Zbl 0853.05037
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.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Erdös, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, (), 122-157
[2] Hajós, G., Über eine konstruktion nicht n-färbbarer graphen, Wiss. Z. martin luther univ. math.-natur. reihe., 10, 116-117, (1961)
[3] Mahadev, N.V.R.; Roberts, F.S.; Santhanakrishnan, P., 3-choosable complete bipartite graphs, ()
[4] Vizing, V.G., Colouring the vertices of a graph in prescribed colours, Diskret. anal., 29, 3-10, (1976), (in Russian)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.