@article { ,
title = {A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs},
abstract = {For a positive integer k, a k-coloring of a graph inline image is a mapping inline image such that inline image whenever inline image. The COLORING problem is to decide, for a given G and k, whether a k-coloring of G exists. If k is fixed (i.e., it is not part of the input), we have the decision problem k-COLORING instead. We survey known results on the computational complexity of COLORING and k-COLORING for graph classes that are characterized by one or two forbidden induced subgraphs. We also consider a number of variants: for example, where the problem is to extend a partial coloring, or where lists of permissible colors are given for each vertex.},
doi = {10.1002/jgt.22028},
eissn = {1097-0118},
issn = {0364-9024},
issue = {4},
journal = {Journal of Graph Theory},
note = {EPrint Processing Status: Full text deposited in DRO},
pages = {331-363},
publicationstatus = {Published},
publisher = {Wiley},
volume = {84},
keyword = {Algorithms and Complexity in Durham (ACiD)},
year = {2017},
author = {Golovach, P.A. and Johnson, M. and Paulusma, D. and Song., J.}
}