We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Computing role assignments of chordal graphs.

Hof, P van 't and Paulusma, Daniel and Rooij, J.M.M. van (2010) 'Computing role assignments of chordal graphs.', Theoretical computer science., 411 (40-42). pp. 3601-3613.


In social network theory, a simple graph G is called k-role assignable if there is a surjective mapping that assigns a number from {1,…,k}, called a role, to each vertex of G such that any two vertices with the same role have the same sets of roles assigned to their neighbors. The decision problem whether such a mapping exists is called the k-Role Assignment problem. This problem is known to be NP-complete for any fixed k≥2. In this paper, we classify the computational complexity of the k-Role Assignment problem for the class of chordal graphs. We show that for this class the problem can be solved in linear time for k=2, but remains NP-complete for any k≥3. This generalizes earlier results by Sheng and answers her open problem.

Item Type:Article
Keywords:Role assignment, Graph homomorphism, Chordal graph, Computational complexity.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:NOTICE: this is the author's version of a work that was accepted for publication in Theoretical computer science.
Date accepted:No date available
Date deposited:07 October 2010
Date of first online publication:September 2010
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar