Graph colourings, subcolourings, and beyond

-- Quentin Chuet (LISN, Galac)

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.

Category: seminars
Tags: Team seminar graphs