A lower bound for the chromatic number of a graph (Q2752204)

Let \(G\) be a connected graph on \(n\) vertices with adjacency matrix \(A\). \textit{A. J. Hoffman} [Graph Theory Appl., 79-91 (1970; Zbl 0221.05061)] showed that the chromatic number of \(G\) is bounded from below by \(1+\lambda_1/|\lambda_n|\), where \(\lambda_1\) and \(\lambda_n\) are the largest and smallest eigenvalues of \(A\), respectively. NEWLINENEWLINENEWLINELet \(D\) be any diagonal matrix with positive entries, such that \(D+A\) is positive semidefinite. It is shown in this paper that the largest eigenvalue of \(D^{-1/2}AD^{-1/2}+I_n\) is a lower bound for the chromatic number of \(G\). The choice \(D=|\lambda_n|I_n\) yields Hoffman's result as a special case. The author describes a semidefinite program whose solution gives a choice for \(D\) which generally yields an even better lower bound for the chromatic number. Finally, an algorithm for approximating a solution to the semidefinite program to within any desired accuracy is presented.NEWLINENEWLINEFor the entire collection see [Zbl 0964.00028].