MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
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$? – Shahrooz Janbaz Jan 17 '12 at 17:50
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. – Shahrooz Janbaz Jan 17 '12 at 18:20
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 – Clive elphick Jan 17 '12 at 21:29
Just curious - to which journal did you submit the paper? – Felix Goldberg Sep 21 '12 at 14:17
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 – Gerhard Paseman Sep 21 '12 at 15:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.