Use este identificador para citar o ir al link de este elemento:
http://hdl.handle.net/1843/74420| Tipo: | Artigo de Periódico |
| Título: | Colouring the Normalized Laplacian |
| Título(s) alternativo(s): | Colorindo o Laplaciano Normalizado |
| Autor(es): | Gabriel de Morais Coutinho Rafael Grandsire Célio Passos |
| Resumen: | 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. |
| Asunto: | Álgebra Linear Teoria dos Grafos |
| Idioma: | eng |
| País: | Brasil |
| Editor: | Universidade Federal de Minas Gerais |
| Sigla da Institución: | UFMG |
| Departamento: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
| Tipo de acceso: | Acesso Aberto |
| Identificador DOI: | https://doi.org/10.1016/j.entcs.2019.08.031 |
| URI: | http://hdl.handle.net/1843/74420 |
| Fecha del documento: | 2019 |
| metadata.dc.url.externa: | https://www.sciencedirect.com/science/article/pii/S1571066119300817 |
| metadata.dc.relation.ispartof: | Electronic Notes in Theoretical Computer Science |
| Aparece en las colecciones: | Artigo de Periódico |
archivos asociados a este elemento:
| archivo | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| Colouring the Normalized Laplacian.pdfA.pdf | 159.43 kB | Adobe PDF | Visualizar/Abrir |
Los elementos en el repositorio están protegidos por copyright, con todos los derechos reservados, salvo cuando es indicado lo contrario.