A Spectral Lower Bound on Chromatic Numbers using p-Energy

Let AG be the adjacency matrix of a simple graph G, and let χ(G), χf(G), χq(G), ξ(G) and ξf(G) denote its chromatic number, fractional chromatic number, quantum chromatic number, orthogonal rank and projective rank, respectively. For p ≥ 0, we define the positive and negative p-energies of G by Eₚ⁺(G) = ∑λᵢ > 0 λᵢᵖ, Eₚ⁻(G) = ∑λᵢ < 0 |λᵢ|ᵖ, where λ₁ ≥ ⋯ ≥ λₙ are the eigenvalues of AG. We prove that for all p ≥ 0, $$ χ(G) ≥ \{χ_f(G), χ_q(G), ξ(G) \} ≥ ξ_f(G) ≥ 1 + max\{ E_p^+(G)/E_p^-(G), E_p^-(G)/E_p^+(G) \}1/|p - 1|. $$ This result unifies and strengthens a series of existing bounds corresponding to the cases $ p ∈ \{0, 2, ∞\} $. In particular, the case $ p = 0 $ yields the inertia bound $$ χ_f(G) ≥ ξ_f(G) ≥1 + max\{n^+/n^-, n^-/n^+\}, $$ where $ n^+ $ and $ n^- $ denote the number of positive and negative eigenvalues of $ A_G $, respectively. This resolves two conjectures of Elphick and Wocjan. We also demonstrate that for certain graphs, non-integer values of $ p $ provide sharper lower bounds than existing spectral bounds. As an example, we determine $ χ_q $ for the Tilley graph, which cannot be achieved using existing (unweighted) $p$-energy bounds. Our proof employs a novel synthesis of linear algebra and measure-theoretic tools, which allows us to surpass existing spectral bounds.