Efficient spectral bounds on the chromatic number of Hamming, Johnson, and Kneser graph powers
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915708416294912 |
|---|---|
| author | Steinke, Finn A. Varona, Luis M. B. |
| author_facet | Steinke, Finn A. Varona, Luis M. B. |
| contents | 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 to efficiently compute the entire spectra. We then apply dynamic programming to compute the Hoffman bounds for $H(n, q)^p$, $J(n, k)^p$, and $K(n, k)^p$ in $O(np)$, $O(kp)$, and $O(k^2)$ time, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_01962 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Efficient spectral bounds on the chromatic number of Hamming, Johnson, and Kneser graph powers Steinke, Finn A. Varona, Luis M. B. Combinatorics 05C15 (Primary) 05C50, 90C39 (Secondary) 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 to efficiently compute the entire spectra. We then apply dynamic programming to compute the Hoffman bounds for $H(n, q)^p$, $J(n, k)^p$, and $K(n, k)^p$ in $O(np)$, $O(kp)$, and $O(k^2)$ time, respectively. |
| title | Efficient spectral bounds on the chromatic number of Hamming, Johnson, and Kneser graph powers |
| topic | Combinatorics 05C15 (Primary) 05C50, 90C39 (Secondary) |
| url | https://arxiv.org/abs/2601.01962 |