@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}
}

{"_id":"qK8NbJdcJKFxfqq2g","bibbaseid":"golovach-johnson-paulusma-song-asurveyonthecomputationalcomplexityofcolouringgraphswithforbiddensubgraphs-2014","downloads":0,"creationDate":"2015-06-13T03:15:11.841Z","title":"A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs","author_short":["Golovach, P.<nbsp>A.","Johnson, M.","Paulusma, D.","Song, J."],"year":2014,"bibtype":"article","biburl":"https://dl.dropboxusercontent.com/u/9343921/library.bib","bibdata":{"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.","Johnson, Matthew","Paulusma, Danïel","Song, Jian"],"author_short":["Golovach, P.<nbsp>A.","Johnson, M.","Paulusma, D.","Song, J."],"bibtex":"@article{ Golovach2014,\n 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.},\n archiveprefix = {arXiv},\n arxivid = {1407.1482v4},\n author = {Golovach, Petr A. and Johnson, Matthew and Paulusma, Danï{e}l and Song, Jian},\n eprint = {1407.1482v4},\n 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},\n journal = {arXiv preprint},\n month = {July},\n title = {{A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs}},\n 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},\n year = {2014}\n}","bibtype":"article","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","id":"Golovach2014","journal":"arXiv preprint","key":"Golovach2014","month":"July","title":"A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs","type":"article","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","bibbaseid":"golovach-johnson-paulusma-song-asurveyonthecomputationalcomplexityofcolouringgraphswithforbiddensubgraphs-2014","role":"author","urls":{"Paper":"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"},"downloads":0},"search_terms":["survey","computational","complexity","colouring","graphs","forbidden","subgraphs","golovach","johnson","paulusma","song"],"keywords":[],"authorIDs":[],"dataSources":["DJNCDySdY8tyWWhKE"]}