Skip to main content
6 of 9
Paper published in the Electronic jour
Andrés E. Caicedo
  • 32.5k
  • 5
  • 133
  • 240

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