The complexity of tropical graph homomorphisms

Florent Foucaud, Ararat Harutyunyan, Pavol Hell +3

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,…