Proof of a Conjectured Spectral Upper Bound on the Chromatic Number of a Graph
Let G be a simple graph on n vertices and m edges with chromatic number χ, and let λ_n denote the least adjacency eigenvalue. Solving a conjecture of Fan, Yu and Wang, we prove that when 3χn-1, the chromatic number satisfies the following upper bound: χ (n2+1+λ_n) + (n2+1+λ_n)^2-4(λ_n+1)(λ_n+n2), with equality if and only if G (K_χ2 n-χ2K_1) (K_χ2 n-χ2K_1), where both n and χ are even. This extends the validity of Fan-Yu-Wang’s bound from the range 3χn2 to the full range 3χn-1. We also compare this bound with the well-known bound due to Wilf that χ 1 + λ_1, where λ_1 denotes the largest eigenvalue. In particular we show that while Wilf’s bound is an upper bound for some parameters larger than χ, this bound using λ_n is not an upper bound for these parameters. We conclude with a similar conjectured upper bound for χ(G), which uses m in place of n. , number=2, journal=The Electronic Journal of Combinatorics, author=Tang, Quanyu and Elphick, Clive, year=2026, month=Jun., pages=#P2.65