Proof of a Conjectured Spectral Upper Bound on the Chromatic Number of a Graph
The Electronic Journal of Combinatorics · 19.06.2026 · 33 (2)
DOI: 10.37236/15125 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 19.06.2026. Verfasst von Quanyu Tang und 1 weiteren Autor:innen.
Abstract (Originalsprache)
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, 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\tfrac{n-\chi}{2}K_1\right) \vee \left(K_{\frac{\chi}{2}}\cup\tfrac{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$.
Zitieren
APA
Tang, Q., & Elphick, C. (2026). Proof of a Conjectured Spectral Upper Bound on the Chromatic Number of a Graph. The Electronic Journal of Combinatorics, 33(2). https://doi.org/10.37236/15125
Vancouver
Tang Q, Elphick C. Proof of a Conjectured Spectral Upper Bound on the Chromatic Number of a Graph. The Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/15125
BibTeX
@article{Tang2026,
author = {Tang, Quanyu and Elphick, Clive},
title = {Proof of a Conjectured Spectral Upper Bound on the Chromatic Number of a Graph},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {2},
doi = {10.37236/15125}
}
EUVIMED