Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 + S+/S- <= q?

The chromatic number cannot be replaced with the clique number in this conjecture, because the Coxeter graph provides a counter-example. Experimentally this bound is sometimes better and sometimes worse than the Hoffman lower bound for the chromatic number.

Pawel Wocjan and I have published a paper in the Electronic Journal of Combinatorics, Volume 20, issue 3 entitled "New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix".

In the paper we prove that S+/S- <= q. We also prove a generalisation of Hoffman's lower bound, which uses all eigenvalues.In both cases the proof is derived using a new characterisation of q-chromatic graphs. The paper includes empirical evidence on the performance of the new bounds for named and random graphs. Some progress has therefore been made but my original conjecture remains a conjecture.

share|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 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 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
show 3 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

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.