  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 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\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. We then improve this value to $\Theta((\Delta-1)^{\frac{k}{12}})$.
