Every planar graph is 5-choosable. (English) Zbl 0805.05023

Thomassen, Carsten

J. Comb. Theory, Ser. B 62, No. 1, 180-181 (1994).

The author shows the 5-choosability of planar graphs. This result was conjectured by V. G. Vizing [Kibernetika, Kiev 1975, Nr. 1, 135-138 (1975; Zbl 0309.90060)], and independently by P. Erdős, A. L. Rubin and H. Taylor [Combinatorics, graph theory and computing, Proc. West Coast Conf., Arcata/Cal. 1979, 125-157 (1980; Zbl 0469.05032)].

Reviewer: Liu Yanpei (Beijing)

MSC:

05C15	Coloring of graphs and hypergraphs
05C10	Planar graphs; geometric and topological aspects of graph theory

Keywords:

list coloring; choosability; planar graphs