Efficient spectral bounds on the chromatic number of Hamming, Johnson, and Kneser graph powers

Abstract

We investigate spectral lower bounds on the chromatic number $\chi$ 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 $\chi$ can, in principle, be applied to any graph, naïve computation requires $O(q^{3n})$ time for $H(n,q{)}^p$ and $O(({}_n{C}_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.

18 pages