We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Computing vertex-surjective homomorphisms to partially reflexive trees.

Golovach, P.A. and Paulusma, Daniel and Song, J. (2012) 'Computing vertex-surjective homomorphisms to partially reflexive trees.', Theoretical computer science., 457 . pp. 86-100.


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.

Item Type:Article
Keywords:Graph homomorphism, Surjectivity, Computational complexity.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:NOTICE: this is the author’s version of a work that was accepted for publication in Theoretical computer science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Theoretical computer science, 457, 2012, 10.1016/j.tcs.2012.06.039
Date accepted:No date available
Date deposited:17 April 2013
Date of first online publication:October 2012
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar