Colouring the normalized Laplacian
From MaRDI portal
Publication:6327271
Abstract: We apply Cauchy's interlacing theorem to derive some eigenvalue bounds to the chromatic number using the normalized Laplacian matrix, including a combinatorial characterization of when equality occurs. Further, we introduce some new expansion type of parameters which generalize the Cheeger constant of a graph, and relate them to the colourings which meet our eigenvalue bound with equality. Finally, we exhibit a family of examples, which include the graphs that appear in the statement of the ErdH{o}s-Faber-Lov'asz conjecture.
This page was built for publication: Colouring the normalized Laplacian
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6327271)
