{"id":"arxiv/2601.01962","url":"https://arxiv.org/abs/2601.01962","tags":["math.CO"],"score":0,"title":"Efficient spectral bounds on the chromatic number of Hamming, Johnson, and Kneser graph powers","domain":"math.CO","source":"arxiv","authors":["Finn A. Steinke","Luis M. B. Varona"],"reviews":0,"subject":"math.CO","summary":"We investigate spectral lower bounds on the chromatic number $χ$ of Hamming graph powers $H(n, q)^p$, Johnson graph powers $J(n, k)^p$, and Kneser graph powers $K(n, k)^p$ providing the first computationally feasible nontrivial results. While the classical Hoffman bound on $χ$ can, in principle, be applied to any graph, naïve computation requires $O(q^{3n})$ time for $H(n, q)^p$ and $O(({}_nC_k)^3)$ time for both $J(n, k)^p$ and $K(n, k)^p$. We thus express the adjacency eigenvalues of these graphs in terms of hypergeometric orthogonal polynomials, exploiting recurrence relations that arise…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-05","reactions":{}}