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

Abstract

For a graph with largest normalized Laplacian eigenvalue ${\lambda }_N$ and (vertex) coloring number $\chi$, it is known that ${\lambda }_N\ge \chi /(\chi -1)$. Here we prove properties of graphs for which this bound is sharp, and we study the multiplicity of $\chi /(\chi -1)$. We then describe a family of graphs with largest eigenvalue $\chi /(\chi -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 ${\lambda }_N$ in terms of $\chi$.

Added new results in Section 3 (Theorem 3.12 - Proposition 3.16)