@book{612d65a479f6423faeb9146ef11f982e,

title = "The computational complexity of the role assignment problem",

abstract = "A graph $G$ is $R$-role assignable if there is a locally surjective homomorphism from $G$ to $R$, i.e. a vertex mapping $r:V_G\to V_R$, such that the neighborhood relation is preserved: $r(N_G(u)) = N_R(r(u))$. Kristiansen and Telle conjectured that the decision problem whether such a mapping exists is an {\sf NP}-complete problem for any connected graph $R$ on at least three vertices. In this paper we prove the conjecture and show further corollaries for disconnected graphs and related problems.",

keywords = "METIS-213722, MSC-03D15, EWI-3488, IR-65854, MSC-05C15",

author = "J. Fiala and Dani{\"e}l Paulusma",

note = "Imported from MEMORANDA",

year = "2003",

language = "Undefined",

isbn = "0169-2690",

series = "Memorandum Afdeling TW",

publisher = "University of Twente, Department of Applied Mathematics",

number = "1668",

}