A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs. Golovach, P.&nbsp;A., Johnson, M., Paulusma, D., & Song, J. arXiv preprint, July, 2014.
For a positive integer \$k\$, a \$k\$-colouring of a graph \$G=(V,E)\$ is a mapping \$c: V\backslash rightarrow\backslash\1,2,\backslash ldots,k\backslash\\$ such that \$c(u)\backslash neq c(v)\$ whenever \$uv\backslash in E\$. The Colouring problem is to decide, for a given \$G\$ and \$k\$, whether a \$k\$-colouring of \$G\$ exists. If \$k\$ is fixed (that is, it is not part of the input), we have the decision problem \$k\$-Colouring instead. We survey known results on the computational complexity of Colouring and \$k\$-Colouring 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 colouring, or where lists of permissible colours are given for each vertex.
@article{ Golovach2014,
abstract = {For a positive integer \$k\$, a \$k\$-colouring of a graph \$G=(V,E)\$ is a mapping \$c: V\backslash rightarrow\backslash\{1,2,\backslash ldots,k\backslash\}\$ such that \$c(u)\backslash neq c(v)\$ whenever \$uv\backslash in E\$. The Colouring problem is to decide, for a given \$G\$ and \$k\$, whether a \$k\$-colouring of \$G\$ exists. If \$k\$ is fixed (that is, it is not part of the input), we have the decision problem \$k\$-Colouring instead. We survey known results on the computational complexity of Colouring and \$k\$-Colouring 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 colouring, or where lists of permissible colours are given for each vertex.},
archiveprefix = {arXiv},
arxivid = {1407.1482v4},
author = {Golovach, Petr A. and Johnson, Matthew and Paulusma, Danï{e}l and Song, Jian},
eprint = {1407.1482v4},
file = {:home/anhduc/Desktop/Dropbox/Mendeley Desktop/A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs - Golovach et al. - 2014.pdf:pdf},
journal = {arXiv preprint},
month = {July},
title = {{A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs}},
url = {https://www.dropbox.com/sh/v4blv7sito3opzn/AADCVtD660xV1EDCA4HaSv8Wa/A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs - Golovach et al. - 2014.pdf?dl=0},
year = {2014}
}