A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs. Golovach, P. A., Johnson, M., Paulusma, D., & Song, J. arXiv preprint, July, 2014.
A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs [link]Paper  abstract   bibtex   
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, Danï{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}
}

Downloads: 0