correction to formula in last line

Source Link

edit approved Aug 20, 2015 at 8:13

1
2
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 + \frac{S_{+}(G)}{S_{-}(G)} \leq q$?

The chromatic number cannot be replaced with the clique number in this conjecture, because the Coxeter graph provides a counter-example. This bound is incomparable with the Hoffman lower bound for the chromatic number.

UPDATE: Ando and Lin have proved this conjecture in "Proof of a conjectured lower bound on the chromatic number of a graph", to be published soon in Linear Algebra and its Applications. They also prove that $1 + \frac{S_{+}(G)}{S_{-}(G)} \leq q$$1 + \frac{S_{-}(G)}{S_{+}(G)} \leq q$.

fixed grammar, corrected spelling, improved formatting

Source Link

edit approved Aug 19, 2015 at 15:43

the_fox

347
3
14

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

Let S+(G)$S_{+}(G)$ denote the sum of the squares of the positive eigenvalues of the adjacency matrix of a graph G$G$. Let S-(G)$S_{-}(G)$ denote the sum of the squares of the negative eigenvalues and q$q$ the chromatic number. Is Is it true that 1 + S+/S- <= q$1 + \frac{S_{+}(G)}{S_{-}(G)} \leq q$?

The chromatic number cannot be replaced with the clique number in this conjecture, because the Coxeter graph provides a counter-example. This bound is incomparable with the Hoffman lower bound for the chromatic number.

UPDATE: Ando and Lin have proved this conjecture in "Proof of a conjectured lower bound on the chromatic number of a graph", to be published in Linear Algebra and its Applications. They also prove that 1 + S-/S+ <= q$1 + \frac{S_{+}(G)}{S_{-}(G)} \leq q$.

conjecture now proved

Source Link

edit approved Aug 19, 2015 at 15:13

Community Bot

1
2
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 thisThis bound is sometimes better and sometimes worse thanincomparable with the Hoffman lower bound for the chromatic number.

Pawel WocjanUPDATE: Ando and ILin have published a paperproved this conjecture in the Electronic Journal"Proof 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'sconjectured 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 performancechromatic number of the new bounds for nameda graph", to be published in Linear Algebra and random graphsits Applications. Some progress has therefore been made but my original conjecture remains a conjectureThey also prove that 1 + S-/S+ <= q.

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.

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. This bound is incomparable with the Hoffman lower bound for the chromatic number.

UPDATE: Ando and Lin have proved this conjecture in "Proof of a conjectured lower bound on the chromatic number of a graph", to be published in Linear Algebra and its Applications. They also prove that 1 + S-/S+ <= q.