Graph Colouring with Distances
Jan van den Heuvel, London School of Economics
Graphs are often used to model situations where the vertices represent events, and edges represent some kind of influence between two events. In such situations, graph colouring is a natural concept if this influence forces vertices to be different. But what if the influence spreads itself further than just to adjacent vertices?
Such behaviour can be modelled using distance colouring. Then we require vertices of a graph to receive a different colour if they have at most some distance k in the graph; a so called distance-k colouring of the graph. And we can ask what the minimum number of colours needed is for a distance-k colouring of a given graph (or a class of graphs). In this talk we give an overview of some of the recent research in this area.