A Brooks-like result for graph powers

Abstract

Coloring a graph $G$ consists in finding an assignment of colors $c:V(G)\to \{1,\dots ,p\}$ such that any pair of adjacent vertices receives different colors. The minimum integer $p$ such that a coloring exists is called the chromatic number of $G$, denoted by $\chi (G)$. We investigate the chromatic number of powers of graphs, i.e. the graphs obtained from a graph $G$ by adding an edge between every pair of vertices at distance at most $k$. For $k=1$, Brooks' theorem states that every connected graph of maximum degree $\Delta ⩾3$ excepted the clique on $\Delta +1$ vertices can be colored using $\Delta$ colors (i.e. one color less than the naive upper bound). For $k⩾2$, a similar result holds: excepted for Moore graphs, the naive upper bound can be lowered by 2. We prove that for $k⩾3$ and for every $\Delta$, we can actually spare $k-2$ colors, excepted for a finite number of graphs. We then improve this value to $\Theta ((\Delta -1{)}^{\frac{k}{12}})$.

9 pages, 2 figures