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

PDF
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:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 213722