Welcome to MathOverflow

Question

8

3

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.

edited Sep 21 at 13:41

asked Jan 7 2012 at 12:37

Clive elphick
81●2

1

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

1

Just curious - to which journal did you submit the paper? – Felix Goldberg Sep 21 at 14:17

1

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

show 3 more comments

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.