Tales of Hoffman

Abstract

Hofmman's bound on the chromatic number of a graph states that $\chi \ge 1-\frac{{\lambda }_1}{{\lambda }_n}$. Here we show that the same bound, or slight modifications of it, hold for several graph parameters related to the chromatic number: the vector coloring number, the $\psi$-covering number and the $\lambda$-clustering number.

short note - 6 pages