Christopher Purcell: Necessary conditions for efficient role colouring

This talk is part of the AScI Large Structures thematic programme seminar series and takes place together with the Complex Systems seminar.

Speaker: Christopher Purcell (Aalto University)

Title: Necessary conditions for efficient role colouring

Abstract:

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 talk is part of the AScI Thematic programme "Challenges in Large Geometric Structures and Big Data" and takes place together with the Complex Systems Seminar. For future seminars see https://aaltoscienceinst.github.io/lsbdseminar/.