HOSIGRA

The complexity of (H, Π )-coloring when input is the class of all signed graphs is considered in the following three papers and it is proved that if the core of (H, Π ) has at least 3 vertices, then the problem in NP-hard and polynomial time otherwise.

• R. C. Brewster, F. Foucaud, P. Hell and R. Naserasr. The complexity of signed and edge-coloured graph homomorphisms. Discrete Mathematics, 340(2) (2017), 223-235.
• R. C. Brewster and M. Siggers. The complexity of signed H-coloring, manuscript.
• F. Foucaud and R. Naserasr. The complexity of signed graph homomorphisms and signed constraint satisfaction. Proceedings of the 11th Latin American Symposium on Theoretical Informatics (LATIN 2014). LNCS 8392:526-537, 2014.

The problem that remains of high interest and widely open is the (H, Π )-coloring when the inputs are restricted to the class of planar graphs.