Eigenvalues and chromatic number of a signed graph (Q2020660)

Let \(G\) be an \(n\)-vertex graph with the adjacency matrix \(A\) which has the eigenvalues \(\lambda_1\geq\dots\geq\lambda_n\), and let \(\chi(G)\) be the chromatic number of \(G\). In this interesting paper the authors generalize two classical spectral lower bounds on the chromatic number \(\chi(G)\geq1+\frac{\lambda_1}{|\lambda_n|}\) [\textit{A. J. Hoffman}, in: Graph theory and its applications. Proceedings of an advanced seminar conducted by the Mathematics Research Center, United States Army, at the University of Wisconsin, Madison, October 13--15, 1969. New York - London: Academic Press. 79--91 (1970; Zbl 0221.05061)] and \(\chi(G)\geq\frac{n}{n-\lambda_1}\) [\textit{D. M. Cvetković}, Publ. Inst. Math., Nouv. Sér. 14(28), 25--38 (1972; Zbl 0271.05111)] from simple graphs to the setting of signed graphs. They also extend the Motzkin-Straus theorem to signed graphs along the way, and further observe that the Wocjan-Elphick's generalization of the Hoffman's bound \(\chi(G)\geq1+\frac{\lambda_1+\cdots+\lambda_k}{|\lambda_n+\cdots+\lambda_{n-k+1}|}\) cannot be extended to signed graphs.