%A Pierron, Théo
%D 2019
%T A Brooks-like result for graph powers
%K
%X Coloring a graph $G$ consists in finding an assignment of colors $c: V(G)\to\{1,\ldots,p\}$ such that any pair of adjacent vertices receive 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 graph of maximum degree $\Delta\geqslant 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\geqslant 2$, a similar result holds: excepted for Moore graphs, the naive upper bound can be lowered by 2. We prove that for $k\geqslant 3$ and for every $\Delta$, we can actually spare $k-2$ colors, excepted for a finite number of graphs.
%U http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1237
%J Acta Mathematica Universitatis Comenianae
%0 Journal Article
%P 1003-1007%V 88
%N 3
%@ 0862-9544
%8 2019-07-31