Computing vertex-surjective homomorphisms to partially reflexive trees

Abstract: A homomorphism from a graph to a graph is a vertex mapping such that and form an edge in whenever and form an edge in . The -Coloring problem is that of testing whether a graph allows a homomorphism to a given graph . A well-known result of Hell and Nešetřil determines the computational complexity of this problem for any fixed graph . We study a natural variant of this problem, namely the Surjective -Coloring problem, which is that of testing whether a graph allows a homomorphism to a graph that is (vertex-)surjective. We classify the computational complexity of this problem for when is any fixed partially reflexive tree. Thus we identify the first class of target graphs for which the computational complexity of Surjective -Coloring can be determined. For the polynomial-time solvable cases we show a number of parameterized complexity results, including in particular ones on graph classes with (locally) bounded expansion. [Copyright &y& Elsevier]