## a new lower bound for the chromatic number of a graph?

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 on arXiv (number 1209.3190) entitled "New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix". We have also submitted the paper to a refereed journal.

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.

-
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 2012 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 2012 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 2012 at 21:29
Just curious - to which journal did you submit the paper? – Felix Goldberg Sep 21 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 at 15:51