A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs

Petr A. Golovach, Matthew Johnson, Daniël Paulusma +1

For a positive integer $k$, a $k$-colouring of a graph $G=(V,E)$ is a mapping $c:V\to \{1,2,...,k\}$ such that $c(u)\ne c(v)$ whenever $uv\in E$. The Colouring problem is…