On the smallest eigenvalues of 3-colorable graphs

2025/05/05 by Zilin Jiang, Zhiyu Wang, Jiang, Zilin +1
Mathematics · Computer Science · #Graph theory and applications #Graph Labeling and Dimension Problems #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2505.03014

Abstract

We prove that the set of the smallest eigenvalues attained by 3-colorable graphs is dense in (-∞, -λ^*), where λ^* = ρ^1/2 + ρ^-1/2 ≈ 2.01980 and ρ is the positive real root of x³ = x + 1. As a consequence, in the context of spherical two-distance sets, our result precludes any further refinement of the forbidden-subgraph method through the chromatic number of signed graphs.

Related

• Forbidden induced subgraphs for graphs and signed graphs with eigenvalues bounded from below
• Coloring 3-Colorable Graphs with Low Threshold Rank
• Strengthened upper bound on the third eigenvalue of graphs
• Beyond the classification theorem of Cameron, Goethals, Seidel, and Shult
• Recent progress on graphs with fixed smallest eigenvalue