Clique and chromatic numbers of graph powers: spectral bounds and anticodes
Abstract
Using spectral and polynomial methods, we show several sharp spectral bounds for the clique and chromatic numbers of graph powers that only use spectral information from the original graph. In particular, we strengthen earlier spectral-radius estimates to obtain an asymptotically sharp colouring bound for general graph powers, and prove a sharp bound for powers of line graphs with a complete characterisation of equality. We also develop polynomial methods yielding upper and lower bounds for clique numbers of graph powers. Regarding the connection between the clique and coloring parameters of graph powers, we propose a spectral analogue of Wegner's conjecture, determine the extremal values for graph squares, and establish the conjecture for all powers when the spectral-radius bound is sufficiently small. Finally, we connect our spectral polynomial method with coding theory: we prove that for distance-regular graphs, optimisation over the adjacency algebra recovers Delsarte's linear programming bound for anticodes.
Related
- Optimization and complexity of inertia-type bounds on the independence and chromatic numbers of graph powers
- Local Clique Covers and Chromatic Number
- Bounded chromatic number of graphs with small clique number and large minimum degree
- On the difference between clique partition and clique covering numbers
- Cayley Tournaments Simultaneously Critical for the Clique and Dichromatic Numbers
BibTeX
@misc{abiad2026clique,
title = {{Clique and chromatic numbers of graph powers: spectral bounds and anticodes}},
author = {Aida Abiad and Gabriel Coutinho and Hitesh Kumar and Emanuel Juliano and Michael Tait},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13852},
eprint = {2610.13852},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13852},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Clique and chromatic numbers of graph powers: spectral bounds and anticodes
AU - Aida Abiad
AU - Gabriel Coutinho
AU - Hitesh Kumar
AU - Emanuel Juliano
AU - Michael Tait
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13852
UR - https://arxiv.org/abs/2610.13852
AB - Using spectral and polynomial methods, we show several sharp spectral bounds for the clique and chromatic numbers of graph powers that only use spectral information from the original graph. In particular, we strengthen earlier spectral-radius estimates to obtain an asymptotically sharp colouring bound for general graph powers, and prove a sharp bound for powers of line graphs with a complete characterisation of equality. We also develop polynomial methods yielding upper and lower bounds for clique numbers of graph powers. Regarding the connection between the clique and coloring parameters of graph powers, we propose a spectral analogue of Wegner's conjecture, determine the extremal values for graph squares, and establish the conjecture for all powers when the spectral-radius bound is sufficiently small. Finally, we connect our spectral polynomial method with coding theory: we prove that for distance-regular graphs, optimisation over the adjacency algebra recovers Delsarte's linear programming bound for anticodes.
ER -