13
$\begingroup$

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

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ 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$? $\endgroup$
    – Shahrooz
    Commented Jan 17, 2012 at 17:50
  • $\begingroup$ 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. $\endgroup$
    – Shahrooz
    Commented Jan 17, 2012 at 18:20
  • 1
    $\begingroup$ Just curious - to which journal did you submit the paper? $\endgroup$
    – Felix Goldberg
    Commented Sep 21, 2012 at 14:17
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Sep 21, 2012 at 15:51
  • 1
    $\begingroup$ The above-cited paper of Clive Elphick and Pawel Wojcan seems to be this one: combinatorics.org/ojs/index.php/eljc/article/view/v20i3p39 . The paper of Ando and Lin is here web.uvic.ca/~linm/chromatic.pdf $\endgroup$
    – j.c.
    Commented Mar 11, 2017 at 11:15

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .