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 (2009) 'Computing role assignments of chordal graphs.', in Fundamentals of computation theory : 17th International Symposium, FCT 2009, Wrocław, Poland, September 2-4, 2009. Proceedings. Berlin ; Heidelberg: Springer, pp. 193-204. Lecture notes in computer science. (5699).


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 becomes polynomially solvable for k = 2, but remains NP-complete for any k ≥ 3. This generalizes results of Sheng and answers his open problem.

Item Type:Book chapter
Full text:Full text not available from this repository.
Publisher Web site:
Date accepted:No date available
Date deposited:No date available
Date of first online publication:September 2009
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar