At the end of the spectrum: Chromatic bounds for the largest eigenvalue of the normalized Laplacian

2024/02/14 by Lies Beers, Beers, Lies, Raffaella Mulas +1 · 2 citations
Computer Science · Mathematics · #Advanced Mathematical Modeling in Engineering #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Spectral Theory (math.SP) #Spectral Theory in Mathematical Physics

paper · pdf · doi:10.48550/arxiv.2402.09160

openalex publication_date 2024/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a graph with largest normalized Laplacian eigenvalue λ_N and (vertex) coloring number χ, it is known that λ_N≥ χ/(χ-1). Here we prove properties of graphs for which this bound is sharp, and we study the multiplicity of χ/(χ-1). We then describe a family of graphs with largest eigenvalue χ/(χ-1). We also study the spectrum of the 1-sum of two graphs (also known as graph joining or coalescing), with a focus on the maximal eigenvalue. Finally, we give upper bounds on λ_N in terms of χ.

Cited by

• Fair and Tolerant (FAT) Graph Colorings
• Hoffman colorability of (strongly) regular graphs

Related

• A few properties of the eigenvalues of normalized graph Laplacian
• Unified spectral bounds on the chromatic number
• Chromatic number and spectral radius
• Two conjectures in spectral graph theory involving the linear combinations of graph eigenvalues
• Bounding the sum of the largest signless Laplacian eigenvalues of a graph