Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/74420| Type: | Artigo de Periódico |
| Title: | Colouring the Normalized Laplacian |
| Other Titles: | Colorindo o Laplaciano Normalizado |
| Authors: | Gabriel de Morais Coutinho Rafael Grandsire Célio Passos |
| 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 point out a connection to the Erdős-Faber-Lovász conjecture. |
| Abstract: | Aplicamos o teorema do entrelaçamento de Cauchy para derivar alguns limites de autovalor para o número cromático usando a matriz Laplaciana normalizada, incluindo uma caracterização combinatória de quando ocorre a igualdade. Além disso, introduzimos alguns novos tipos de parâmetros de expansão que generalizam a constante de Cheeger de um gráfico e os relacionam com as colorações que atendem ao nosso autovalor vinculado à igualdade. Por fim, apontamos uma ligação com a conjectura de Erdős-Faber-Lovász. |
| Subject: | Álgebra Linear Teoria dos Grafos |
| language: | eng |
| metadata.dc.publisher.country: | Brasil |
| Publisher: | Universidade Federal de Minas Gerais |
| Publisher Initials: | UFMG |
| metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
| Rights: | Acesso Aberto |
| metadata.dc.identifier.doi: | https://doi.org/10.1016/j.entcs.2019.08.031 |
| URI: | http://hdl.handle.net/1843/74420 |
| Issue Date: | 2019 |
| metadata.dc.url.externa: | https://www.sciencedirect.com/science/article/pii/S1571066119300817 |
| metadata.dc.relation.ispartof: | Electronic Notes in Theoretical Computer Science |
| Appears in Collections: | Artigo de Periódico |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Colouring the Normalized Laplacian.pdfA.pdf | 159.43 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.