New Eigenvalue Bound for the Fractional Chromatic Number

2022/11/08 by Guo, Krystal, Spiro, Sam
#05C50 #05C72 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2211.04499

Abstract

Given a graph G, we let s⁺(G) denote the sum of the squares of the positive eigenvalues of the adjacency matrix of G, and we similarly define s^-(G). We prove that χ_f(G)≥ 1+max\(s⁺(G))/(s^-(G)),(s^-(G))/(s⁺(G))\ and thus strengthen a result of Ando and Lin, who showed the same lower bound for the chromatic number χ(G). We in fact show a stronger result wherein we give a bound using the eigenvalues of G and H whenever G has a homomorphism to an edge-transitive graph H. Our proof utilizes ideas motivated by association schemes.

Related

• A Spectral Lower Bound on Chromatic Numbers using p-Energy
• Proof of a conjectured spectral upper bound on the chromatic number of a graph
• Sums of squares of eigenvalues and the vector chromatic number
• Unified spectral bounds on the chromatic number
• An eigenvalue bound for the fractional chromatic number