most recent 30 from http://mathoverflow.net 2013-05-25T07:50:56Z http://mathoverflow.net/feeds/question/85126 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/85126/a-new-lower-bound-for-the-chromatic-number-of-a-graph Clive elphick 2012-01-07T12:37:29Z 2012-11-04T18:22:01Z

<p>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- &lt;= q?</p> <p>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.</p> <p>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.</p> <p>In the paper we prove that S+/S- &lt;= 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.</p>