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

Finn A. Steinke, Luis M. B. Varona

We investigate spectral lower bounds on the chromatic number $\ddot{I}‡$ of Hamming graph powers $H(n,q{)}^p$, Johnson graph powers $J(n,k{)}^p$, and Kneser graph powers $K(n,k{)}^p$ providi…