Colouring the Normalized Laplacian

Página do item simplificado
dc.creatorGabriel de Morais Coutinho
dc.creatorRafael Grandsire
dc.creatorCélio Passos
dc.date.accessioned2024-08-20T20:34:16Z
dc.date.accessioned2025-09-08T23:29:07Z
dc.date.available2024-08-20T20:34:16Z
dc.date.issued2019
dc.description.abstractAplicamos 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.
dc.format.mimetypepdf
dc.identifier.doihttps://doi.org/10.1016/j.entcs.2019.08.031
dc.identifier.issn15710661
dc.identifier.urihttps://hdl.handle.net/1843/74420
dc.languageeng
dc.publisherUniversidade Federal de Minas Gerais
dc.relation.ispartofElectronic Notes in Theoretical Computer Science
dc.rightsAcesso Aberto
dc.subjectÁlgebra Linear
dc.subjectTeoria dos Grafos
dc.subject.otherAlgebras, Linear
dc.subject.otherGraph Theory
dc.titleColouring the Normalized Laplacian
dc.title.alternativeColorindo o Laplaciano Normalizado
dc.typeArtigo de periódico
local.citation.epage354
local.citation.spage345
local.citation.volume346
local.description.resumoWe 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.
local.publisher.countryBrasil
local.publisher.departmentICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
local.publisher.initialsUFMG
local.url.externahttps://www.sciencedirect.com/science/article/pii/S1571066119300817

Arquivos

Pacote original

Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Colouring the Normalized Laplacian.pdfA.pdf
Tamanho:
159.43 KB
Formato:
Adobe Portable Document Format
Baixar

Licença do pacote

Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
License.txt
Tamanho:
1.99 KB
Formato:
Plain Text
Descrição:
Baixar

Coleções

Artigo de Periódico

Logo UFMG