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. [ABSTRACT FROM AUTHOR]