Use este identificador para citar ou linkar para este item:
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 |
| Resumo: | 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. |
| Assunto: | Álgebra Linear Teoria dos Grafos |
| Idioma: | eng |
| País: | Brasil |
| Editor: | Universidade Federal de Minas Gerais |
| Sigla da Instituição: | UFMG |
| Departamento: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
| Tipo de Acesso: | Acesso Aberto |
| Identificador DOI: | https://doi.org/10.1016/j.entcs.2019.08.031 |
| URI: | http://hdl.handle.net/1843/74420 |
| Data do 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 nas coleções: | Artigo de Periódico |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| Colouring the Normalized Laplacian.pdfA.pdf | 159.43 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.