Colouring the normalized Laplacian
From MaRDI portal
Publication:6327271
DOI10.1016/J.ENTCS.2019.08.031arXiv1910.06947WikidataQ113317401 ScholiaQ113317401MaRDI QIDQ6327271FDOQ6327271
Authors: Gabriel Coutinho, Rafael Grandsire, Célio Passos 
Publication date: 15 October 2019
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)
