Proof of a conjectured spectral upper bound on the chromatic number of a graph

Abstract

Let $G$ be a simple graph on $n$ vertices and $m$ edges with chromatic number $\chi$, and let ${\lambda }_n$ denote the least adjacency eigenvalue. Solving a conjecture of Fan, Yu and Wang~[Electron. J. Combin., 2012], we prove that when $3\le \chi \le n-1$, the chromatic number satisfies the following upper bound: $$\chi \le \left(\frac{n}{2}+1+{\lambda }_n\right)+\sqrt{{\left(\frac{n}{2}+1+{\lambda }_n\right)}^2-4({\lambda }_n+1)\left({\lambda }_n+\frac{n}{2}\right)},$$ with equality if and only if $G\cong \left(K_{\frac{\chi }{2}}\cup \frac{n-\chi }{2}{K}_1\right)\vee \left(K_{\frac{\chi }{2}}\cup \frac{n-\chi }{2}{K}_1\right)$, where both $n$ and $\chi$ are even. This extends the validity of Fan--Yu--Wang's bound from the range $3\le \chi \le \frac{n}{2}$ to the full range $3\le \chi \le n-1$. We also compare this bound with the well-known bound due to Wilf that $\chi \le 1+{\lambda }_1$, where ${\lambda }_1$ denotes the largest eigenvalue. In particular we show that while Wilf's bound is an upper bound for some parameters larger than $\chi$, this bound using ${\lambda }_n$ is not an upper bound for these parameters. We conclude with a similar conjectured upper bound for $\chi (G)$, which uses $m$ in place of $n$.

8 pages. Accepted for publication in the Electronic Journal of Combinatorics; minor revisions following the referees' suggestions