Computing vertex-surjective homomorphisms to partially reflexive trees

Golovach, P.A.; Paulusma, D.; Song, J.

Abstract

A homomorphism from a graph GG to a graph HH is a vertex mapping f:VG→VHf:VG→VH such that f(u)f(u) and f(v)f(v) form an edge in HH whenever uu and vv form an edge in GG. The HH-Coloring problem is that of testing whether a graph GG allows a homomorphism to a given graph HH. A well-known result of Hell and Nešetřil determines the computational complexity of this problem for any fixed graph HH. We study a natural variant of this problem, namely the SurjectiveHH-Coloring problem, which is that of testing whether a graph GG allows a homomorphism to a graph HH that is (vertex-)surjective. We classify the computational complexity of this problem for when HH is any fixed partially reflexive tree. Thus we identify the first class of target graphs HH for which the computational complexity of SurjectiveHH-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.

Citation

Golovach, P., Paulusma, D., & Song, J. (2012). Computing vertex-surjective homomorphisms to partially reflexive trees. Theoretical Computer Science, 457, 86-100. https://doi.org/10.1016/j.tcs.2012.06.039

• Journal Article Type: Article
• Publication Date: Oct 1, 2012
• Deposit Date: Mar 11, 2013
• Publicly Available Date: Apr 17, 2013
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 457
• Pages: 86-100
• DOI: https://doi.org/10.1016/j.tcs.2012.06.039
• Keywords: Graph homomorphism, Surjectivity, Computational complexity.
• Public URL: https://durham-repository.worktribe.com/output/1487633