Colouring the normalized Laplacian

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 cons...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-10
Main Authors: Coutinho, Gabriel, Grandsire, Rafael, Passos, Célio
Format: Article
Language:English
Subjects:
Coloring
Combinatorial analysis
Eigenvalues
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Erdős-Faber-Lovász conjecture.
ISSN:2331-8422
DOI:10.48550/arxiv.1910.06947