The complexity of \(H\)-colouring of bounded degree graphs
Let \(H\) be a fixed graph; an \(H\)-colouring of \(G\) is a mapping \(c:V(G)\rightarrow V(H)\) which preserves adjacency; an \(H\)-colouring of \(G\) is also called a homomorphism of \(G\) to \(H\). In this paper the complexity of the \(H\)-colouring problem restricted to graphs of bounded degree is investigated. For \(H\)-colouring of bounded degree graphs it is pointed out that there exist polynomial algorithms for several of these restricted colouring problems. A conjecture about the complexity of certain cases of the problem is proposed, which states that for graphs of chromatic number three, all situations which are not solvable by the colouring algorithm inherent in the theorem of Brooks are NP-complete. The conjecture is motivated by proving several supporting results.
scientific article; zbMATH DE number 1506821