Open Research Index

Clique and chromatic numbers of graph powers: spectral bounds and anticodes

Aida Abiad, Gabriel Coutinho, Hitesh Kumar, Emanuel Juliano, Michael Tait

arXivarxiv/2610.13852Oct 9, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2610.13852
curl -X POST /api/v1/records/arxiv/2610.13852/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.13852/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'