Galluccio, Anna; Hell, Pavol; Nešetřil, Jaroslav The complexity of \(H\)-colouring of bounded degree graphs. (English) Zbl 0956.05036 Discrete Math. 222, No. 1-3, 101-109 (2000). 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. Reviewer: Ioan Tomescu (Bucureşti) Cited in 2 ReviewsCited in 16 Documents MSC: 05C15 Coloring of graphs and hypergraphs 68R10 Graph theory (including graph drawing) in computer science Keywords:\(H\)-colouring problem; Brooks theorem; bounded degree graph; NP-completeness PDFBibTeX XMLCite \textit{A. Galluccio} et al., Discrete Math. 222, No. 1--3, 101--109 (2000; Zbl 0956.05036) Full Text: DOI