Department of
Applied
Mathematics

The Complexity of Some Restricted H-Colouring Problems

Mark Siggers

Abstract

We look first at the problem of H-Colouring for instances G of bounded degree. Let b(H) be the minimum integer for which the problem of H-Colouring is NP-complete for graphs G of maximum degree 3. We look at bounds on b(H) for various graphs H, and observe that a small alteration of Hell and Ne\v{s}et\v{r}il's proof of the H-colouring dichotomy shows that b(H) is finite for any non-bipartite graph H. This supports a more general conjecture of Feder, Hell, and Huang, about NP-complete homomorphism problems remaining NP-complete even when large enough finite degree constraints are added.

Time permitting, we will also look at some results on the H-colouring problem when restricted to planar instances G.