Postgraduate research students

I am interested in a variation of the colouring problem called the b-chromatic colouring problem. In the b-chromatic colouring problem we seek to assign colours to the vertices of a graphs such that no two adjacent vertices get the same colour. Moreover, for each colour class there must exists a vertex that is adjacent to vertices of every other colour. The b-chromatic number problem asks for the maximum integer k such that a graph G admits a b-chromatic colouring with k colours. The problem is NP-hard in general and bipartite graphs and polynomial time solvable in trees. My reasearch is focus on the algorithmics aspects of the b-chromatic number in different families of graphs. These aspects includes solvability, approximability and complexity of the b-chromatic number in families of graphs such as d-regular, planar and bipartite graphs.

List by: Type | Date

• Professor David Manlove
• Dr Sofiat Olaosebikan