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
Adam Mickiewicz University
Technical University of Denmark, DTU