C. Purcell – Necessary conditions for efficient role colouring

Christopher Purcell (Aalto University)

Monday 2016-05-16 11.00 – 12.00

Lecture room AS3, TUAS building

Necessary conditions for efficient role colouring


A role colouring of a graph is an assignment of colours to its vertices such that two vertices having the same colour have the same set of colours in their respective neighbourhoods. In a network, nodes with similar roles may have similar neighbourhoods in one way or another. A role colouring is an attempt to formalise an aspect of this phenomenon. This talk will focus on the computational complexity of finding such a colouring with a given number of colours. In particular, we have a sequence of infinitely narrowing classes of graphs for which the problem remains NP-hard, and therefore a necessary condition for a polynomial-time solution in a restricted graph class. Joint work with Puck Rombach.

This seminar is organized jointly with the Large Structures seminar.