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

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 χ. Our findings provide insights into the connection between several properties of networks, such as their coloring number, their normalized Laplacian spectrum, and the existence of cut vertices. This has potential applications to the analysis of complex systems such as biological and chemical networks.