Skip to main content

Research Repository

Advanced Search

Computing vertex-surjective homomorphisms to partially reflexive trees

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

Computing vertex-surjective homomorphisms to partially reflexive trees Thumbnail


Authors

P.A. Golovach

J. Song



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

Files

Accepted Journal Article (617 Kb)
PDF

Copyright 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





You might also like



Downloadable Citations