Some Brooks-like results for graph powers

Speaker: Théo Pierron (Masaryk University)

Abstract: Given an integer {$k$}, coloring the {$k$}-th power of a graph means assigning colors to its vertices in such a way that vertices at distance at most {$k$} receive different colors. When {$k$} is 1, we get the standard notion of coloring, and Brooks' theorem states that every connected graph of maximum degree {$D>2$} besides the clique on {$D+1$} vertices can be colored using {$D$} colors (i.e. one color less than the naive upper bound). For {$k > 1$}, a similar result holds: except for Moore graphs, the naive upper bound can be lowered by 2. In this talk, we will show how to extend these results in order to spare more colors when {$k$} increases.

Date and time: 24/04/2020 at 10:00

Recorded talk: https://mediacenter.univ-lyon1.fr/videos/?video=MEDIA200427155904166.