Chromatic number and spectral radius
Preprint
Abstract
Let G be a graph, H be its chromatic number, L be the largest eigenvalue of its Laplacian, and M be the largest eigenvalue of its adjacency matrix. Then, complementing a well-known result of Hoffman, we show that L>=(H/(H-1))MKeywords
All Related Versions
This publication has 3 references indexed in Scilit:
- Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrices of treesDiscrete Mathematics, 2005
- A sharp upper bound on the largest eigenvalue of the Laplacian matrix of a graphLinear Algebra and its Applications, 2002
- Laplacian matrices of graphs: a surveyLinear Algebra and its Applications, 1994