zbMATH — the first resource for mathematics

Graph colorings with local constraints—a survey. (English) Zbl 0923.05027
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)

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
Full Text: DOI Link