# The computational complexity of the role assignment problem

Fiala, J. and Paulusma, D. (2003) The computational complexity of the role assignment problem. [Report]

 Preview

224kB
 Abstract: A graph is -role assignable if there is a locally surjective homomorphism from to , i.e. a vertex mapping , such that the neighborhood relation is preserved: . Kristiansen and Telle conjectured that the decision problem whether such a mapping exists is an -complete problem for any connected graph on at least three vertices. In this paper we prove the conjecture and show further corollaries for disconnected graphs and related problems. Item Type: Report Faculty: Electrical Engineering, Mathematics and Computer Science (EEMCS) Research Group: Link to this item: http://purl.utwente.nl/publications/65854 Export this item as: BibTeXEndNoteHTML CitationReference Manager

Repository Staff Only: item control page

Metis ID: 213722