The complexity of \(H\)-colouring of bounded degree graphs
type: Item
instance of: scholarly article
title: The complexity of \(H\)-colouring of bounded degree graphs
zbMATH Open document ID: 0956.05036
DOI: 10.1016/S0012-365X(00)00009-1
author: A. Galluccio
author: Pavol Hell
author: J. Nešetřil
published in: Discrete Mathematics
publication date: 2001-03-04T00:00:00Z
review text: 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.
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1506821
zbMATH Keywords: \(H\)-colouring problem
zbMATH Keywords: Brooks theorem
zbMATH Keywords: bounded degree graph
zbMATH Keywords: NP-completeness
MaRDI profile type: Publication
full work available at URL: s0012-365x(00)00009-1
OpenAlex ID: W1988205260
Recommended article: Complexity issues on bounded restrictive \(H\)-coloring
Recommended article: Q4414491
Recommended article: On the complexity of H-coloring
Recommended article: Q3758852
Recommended article: \(H\)-coloring degree-bounded (acyclic) digraphs
Recommended article: Dichotomy for bounded degree \(H\)-colouring
Recommended article: On the complexity of \(H\)-colouring planar graphs
Recommended article: Q4427278
Recommended article: The complexity of some graph colouring problems
Recommended article: Q4668721
description: scientific article; zbMATH DE number 1506821