Proving a conjecture concerning chromatic number, size and least eigenvalue

2026/08/04 by Leyou Xu, Bo Zhou
Mathematics · #math.CO

paper · pdf

arxiv created 2026/08/04 · arxiv updated 2026/08/05

Abstract

Let G be a simple nonempty graph with size m, chromatic number χ, and least eigenvalue λ. We prove that χ(χ-1) ≤ (m+1-λ²)+√((m+1-λ²)²-4(λ²-1)(λ²-m)) with equality if and only if G is either a complete graph or a complete bipartite graph, with possibly isolated vertices. The inequality was conjectured recently by Tang and Elphick in [Electron. J. Combin. 33 (2026), #P2.65].

Citations

• Proof of a conjectured spectral upper bound on the chromatic number of a graph
• Upper bounds for the achromatic and coloring numbers of a graph
• Bounds on graph eigenvalues I
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger