Let $S_{+}(G)$ denote the sum of the squares of the positive eigenvalues of the adjacency matrix of a graph $G$. Let $S_{-}(G)$ denote the sum of the squares of the negative eigenvalues and $q$ the chromatic number. Is it true that $1 + \frac{S_{+}(G)}{S_{-}(G)} \leq q$?

The chromatic number cannot be replaced with the clique number in this conjecture, because the Coxeter graph provides a counter-example. This bound is incomparable with the Hoffman lower bound for the chromatic number.

UPDATE: Ando and Lin have proved this conjecture in "Proof of a conjectured lower bound on the chromatic number of a graph", to be published soon in Linear Algebra and its Applications. They also prove that $1 + \frac{S_{-}(G)}{S_{+}(G)} \leq q$.

  • 1
    $\begingroup$ Dear Clive, did you test your inequality for any class of trees or $K_n -{e_1,e_2,...,e_t}$ for some suitable $t$? $\endgroup$
    – Shahrooz
    Jan 17, 2012 at 17:50
  • $\begingroup$ I think about Kneser graphs. We know that for Kneser graph $K_{n:r}$, $q=n-2r+2$ and $m=Cr(n,r)Cr(n-r,r)/2$. Also the eigenvalues of these graphs are determined and are $(-1)^i \times Cr(n-r-i,r-i)$. I think for suitable $n$(sufficiently large) and $r$ you can find a counter example for this inequality. $\endgroup$
    – Shahrooz
    Jan 17, 2012 at 18:20
  • $\begingroup$ Dear Shahrooz, I have tested the conjecture against all named graphs in Wolfram Mathematica 8.0 with up to 50 vertices and found no counter-examples. I have proved the conjecture for KG(n:r) for r = 1,2,3,4. For r > 4 the algebra gets tortuous! What makes you think for large n and r there will be a counter-example? Thanks Clive $\endgroup$ Jan 17, 2012 at 21:29
  • 1
    $\begingroup$ Just curious - to which journal did you submit the paper? $\endgroup$ Sep 21, 2012 at 14:17
  • 1
    $\begingroup$ Stylistically, it is unclear to me which is better: to edit the question and provide a clearly marked update, or to submit an answer which contains an updated answer? Either is better than your current edit. I suggest adding the word "Update" to the start of the relevant paragraph. Gerhard "Ask Me About System Design" Paseman, 2012.09.21 $\endgroup$ Sep 21, 2012 at 15:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.