Conjectured lower bound for the clique number of a graph

Abstract

It is well known that $n/(n-\mu )$, where $\mu$ is the spectral radius of a graph with $n$ vertices, is a lower bound for the clique number. We conjecture that $\mu$ can be replaced in this bound with $\sqrt{s^{+}}$, where $s^{+}$ is the sum of the squares of the positive eigenvalues. We prove this conjecture for various classes of graphs, including triangle-free graphs, and for almost all graphs.

added funding info