New trends in the theory of graph colorings: Choosability and list coloring
Jan Kratochvı́l, Źsolt Tuza, Margit Voigt · DIMACS series in discrete mathematics and theoretical computer science · 1999
We survey recent developments and open problems on graph colorings where the color of each vertex has to be chosen from a restricted set of admissible colors. 1 Preliminaries Graph colorings belong to classical graph theoretical problems that are important both for their practical applications and richness of theoretical results. E.g., the Four Color Conjecture has stimulated research in discrete mathematics for more than hundred years, and the recent computer-aided proofs of extensions of the Four Color Theorem by Robertson et al. highlight Department of Applied Mathematics, Charles University, Malostransk'e n'am. 25, 118 00 Prague, Czech Republic. E-mail: [email protected]. This author acknowledges partial support of Czech research grants GA CR 201/1996/0194 and GAUK 194/1996. y Computer and Automation Institute, Hungarian Academy of Sciences, H--1111 Budapest, Kende u. 13--17, Hungary. E-mail: [email protected]. Research supported in part by the Hungarian Scientific Resea...