Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number (Q2496209): Difference between revisions

Let \(G\) be a graph on \(n\) vertices, \(\chi\) its chromatic number, and \(A\) its adjacency matrix. Let \(\lambda_1\) and \(\lambda_n\) be the largest and least eigenvalue of \(A\). Hoffman's bound [\textit{A.~J.~Hoffmann}, ``On eigenvalues and colorings of graphs'', in: Graph Theory Appl., Proc. Advanced Sem. Wisconsin, Madison 1969, 79--91 (1970; Zbl 0221.05061)] states that \(\chi\geq1-\lambda_1/\lambda_n\). In this paper it is shown that the same bound, or slight modifications of it, hold for several graph parameters related to the chromatic number: the vector coloring number [see \textit{D.~Karger, R.~Motwani} and \textit{M.~Sudan}, J.~ACM 45, 246--265 (1998; Zbl 0904.68116)], the \(\psi\)-covering number (introduced by \textit{A.~Amit, N.~Linial} and \textit{J.~Matoušek} [Random Struct. Algorithms 20, 1--22 (2002; Zbl 0993.05071)]) and the \(\lambda\)-clustering number (introduced in the paper under review).