The complexity of tropical graph homomorphisms

A tropical graph (H, c) consists of a graph H and a (not necessarily proper) vertex-colouring c of H. Given two tropical graphs (G, c(1)) and (H, c), a homomorphism of (G, c(1)) to (H, c) is a standard graph homomorphism of G to H that also preserves the vertex-colours. We initiate the study of the computational complexity of tropical graph homomorphism problems. We consider two settings. First, when the tropical graph (H, c) is fixed; this is a problem called (H, c)-COLOURING. Second, when the colouring of H is part of the input; the associated decision problem is called H-TROPICAL-COLOURING. Each (H, c)-COLOURING problem is a constraint satisfaction problem (CSP), and we show that a complexity dichotomy for the class of (H, c)-COLOURING problems holds if and only if the Feder-Vardi Dichotomy Conjecture for CSPs is true. This implies that (H, c)-COLOURING problems form a rich class of decision problems. On the other hand, we were successful in classifying the complexity of at least certain classes of H-TROPICAL-COLOURING problems. (C) 2017 Elsevier B.V. All rights reserved.