### 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.

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Number of pages | 17 |

ISBN (Print) | 0169-2690 |

Publication status | Published - 2003 |

### Publication series

Name | Memorandum Afdeling TW |
---|---|

Publisher | Department of Applied Mathematics, University of Twente |

No. | 1668 |

ISSN (Print) | 0169-2690 |

### Keywords

- METIS-213722
- MSC-03D15
- EWI-3488
- IR-65854
- MSC-05C15

## Cite this

Fiala, J., & Paulusma, D. (2003).

*The computational complexity of the role assignment problem*. (Memorandum Afdeling TW; No. 1668). Enschede: University of Twente, Department of Applied Mathematics.