A Brooks-like result for graph powers $

Abstract

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 except 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: except 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, except for a finite number of graphs. We then improve this value to Θ((∆ -1) k 12 ).

Matrix algebras with orthogonal Cauchy-like transforms and Toeplitz approximation: a negative result
Dario Fasino, Davide Furchì, Valerio Loi +1
arXiv12 Oct 2026PreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
Clique and chromatic numbers of graph powers: spectral bounds and anticodes
Aida Abiad, Gabriel Coutinho, Hitesh Kumar +2
arXiv9 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
The Zero Forcing Number of Graph Powers
Aida Abiad, Mary Flagg, Sina Ghasemi Nezhad +1
arXiv2 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Graph Powers of Groups
Gabe Cunningham, Igor Minevich
The Electronic Journal of Combinatorics23 Oct 2026Peer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref
Optimization and complexity of inertia-type bounds on the independence and chromatic numbers of graph powers
Aida Abiad, Stan van Hoesel, Valentin Michaux
arXiv17 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@article{pierron2026brookslike,
  title = {{A Brooks-like result for graph powers $}},
  author = {Théo Pierron},
  journal = {European Journal of Combinatorics},
  year = {2026},
  month = sep,
  doi = {10.1016/j.ejc.2023.103822},
  url = {https://hal.science/hal-05745804v1},
  note = {CC BY-NC 4.0},
}

RIS

TY  - JOUR
TI  - A Brooks-like result for graph powers $
AU  - Théo Pierron
PY  - 2026
DA  - 2026/09/17
JO  - European Journal of Combinatorics
DO  - 10.1016/j.ejc.2023.103822
UR  - https://hal.science/hal-05745804v1
AB  - 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 except 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: except 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, except for a finite number of graphs. We then improve this value to Θ((∆ -1) k 12 ).
SN  - 0195-6698
SN  - 1095-9971
ER  -

Abstract

Related

Cite