Graph colourings, subcolourings, and beyond
Time: 14:00 -- Location: LRI, 445
summary: The graph colouring problem is central in Graph Theory: it consists in colouring the vertices
of a graph such that each colour class induces an independent set, using as few colours as possible.
While very difficult to solve exactly, the problem and its worst cases are now understood quite well.
In that regard, colourings have been generalized in various manners: one way colouring can be relaxed
is by loosening the restriction imposed on the colour classes. A subcolouring is a generalized colouring
in which each colour class induces a disjoint union of cliques, or equivalently, connected components
of diameter 1. More generally, we study diameter-t colourings, where each colour class induces connected
components of diameter t (Note that diameter-0 colouring coincides with the original notion of colouring).
Naturally, we also consider radius-t colourings.
In this talk, we take a look at the extremal behaviour of diameter-t and radius-t colourings (for a fixed t)
in relation to the number of vertices and the maximum degree. For the upper bounds, we adapt a classical
yet elegant ball-carving technique. As for the lower bounds, we present various constructions, ranging
from geometric to probabilistic.