A spectral bound for the chromatic number involving the number of edges

From papers

Let GG be a non-empty graph with mm edges, chromatic number χ\chi, and least adjacency eigenvalue λn\lambda_n. The spectral edge-count conjecture.

χ(χ1)(m+1λn2)+(m+1λn2)24(λn21)(λn2m).\chi(\chi-1) \leq (m+1-\lambda_n^2)+\sqrt{(m+1-\lambda_n^2)^2-4(\lambda_n^2-1)(\lambda_n^2-m)}.

This conjecture is motivated by replacing the order parameter in the Fan–Yu–Wang bound with the number of edges, the chromatic-number term by χ(χ1)\chi(\chi-1), and the least eigenvalue by λn2-\lambda_n^2. The supplied text presents it as a conjecture and gives no resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Quanyu Tang and Clive Elphick, “Proof of a conjectured spectral upper bound on the chromatic number of a graph”, arXiv:2511.07712 (2026).

Solutions 0

No solutions have been posted yet.