2019/12/24 by Théo Pierron, Pierron, Théo
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1912.11181
openalex publication_date 2019/12/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Δ\geqslant 3 excepted the clique on Δ+1 vertices can be colored using Δ 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 Δ, we can actually spare k-2 colors, excepted for a finite number of graphs. We then improve this value to Θ((Δ-1)(k)/(12)).