Unified spectral bounds on the chromatic number
Clive H. Elphick, Paweł Wocjan · Discussiones Mathematicae Graph Theory · 2015
One of the best known results in spectral graph theory is the following lower bound on the chromatic number due to Alan Hoffman, where 1 and n are respectively the maximum and minimum eigenvalues of the adjacency matrix: 1 + 1 / - n . We recently generalised this bound to include all eigenvalues of the adjacency matrix.