Graph colorings with local constraints—a survey. (English) Zbl 0923.05027

Tuza, Zsolt

Discuss. Math., Graph Theory 17, No. 2, 161-228 (1997).

This paper surveys the main results on those variants of the chromatic number problem where not only a proper coloring has to be found but some further local restrictions are imposed on the color assignment. Among others the list colorings and the precoloring extensions are considered in detail. Surveying this part of the literature, not only the strongest results are presented but also much of the history. Some typical techniques are illustrated by sketches of proofs. Several open problems are mentioned as well. The contents of this 67-pages-long paper is as follows: (0) Introduction. (1) General results. (2) Vertex degrees. (3) Comparison of coloring parameters. (4) Algorithmic complexity. References.

Reviewer: M.Kubale (Gdańsk)

MSC:

05C15	Coloring of graphs and hypergraphs
05-02	Research exposition (monographs, survey articles) pertaining to combinatorics
68R10	Graph theory (including graph drawing) in computer science

Keywords:

choice number; chromatic number; list colorings; precoloring extensions; complexity