Efficient spectral bounds on the chromatic number of Hamming, Johnson, and Kneser graph powers
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.01962
curl -X POST /api/v1/records/arxiv/2601.01962/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.01962/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'