×

The complexity of \(H\)-colouring of bounded degree graphs. (English) Zbl 0956.05036

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.

MSC:

05C15 Coloring of graphs and hypergraphs
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI