A Brooks-like result for graph powers
share
Coloring a graph G consists in finding an assignment of colors c: V(G)→{1,...,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 χ(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 Δ≥ 3 excepted the clique on Δ+1 vertices can be colored using Δ 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 Δ, we can actually spare k-2 colors, excepted for a finite number of graphs. We then improve this value to Θ((Δ-1)^k/12).
READ FULL TEXT