From distance-2-colourings of graphs to colourings of hypergraphs

Graphs, Hypergraphs, and Computing

04 February 15:30 - 16:30

Jan van den Heuvel - The London School of Economics and Political Science (LSE)

A distance-2-colouring of a graph is a colouring of the vertices in which pairs of vertices at distance at most two must receive a different colour. Another way to define it is as a proper colouring in which vertices in the same neighbourhood all receive a different colour. There has been quite some research on finding good upper bounds on the number of colours needed in such a colouring for certain classes of graphs. More recently it has been shown to be useful to consider more general colourings, where the restrictions apply only to certain subsets of the vertex-neighbourhoods. We report on recent developments in this area, and show how it leads to questions about certain types of colourings of hypergraphs.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to