1. Repositório Institucional da UFMG
  2. Publicações Científicas e Culturais
  3. Artigo de Periódico
Use este identificador para citar ou linkar para este item: http://hdl.handle.net/1843/74420
Registro completo de metadados
Campo DCValorIdioma
dc.creatorGabriel de Morais Coutinhopt_BR
dc.creatorRafael Grandsirept_BR
dc.creatorCélio Passospt_BR
dc.date.accessioned2024-08-20T20:34:16Z-
dc.date.available2024-08-20T20:34:16Z-
dc.date.issued2019-
dc.citation.volume346pt_BR
dc.citation.spage345pt_BR
dc.citation.epage354pt_BR
dc.identifier.doihttps://doi.org/10.1016/j.entcs.2019.08.031pt_BR
dc.identifier.issn15710661pt_BR
dc.identifier.urihttp://hdl.handle.net/1843/74420-
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.pt_BR
dc.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.pt_BR
dc.format.mimetypepdfpt_BR
dc.languageengpt_BR
dc.publisherUniversidade Federal de Minas Geraispt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃOpt_BR
dc.publisher.initialsUFMGpt_BR
dc.relation.ispartofElectronic Notes in Theoretical Computer Sciencept_BR
dc.rightsAcesso Abertopt_BR
dc.subjectAlgebras, Linearpt_BR
dc.subjectGraph Theorypt_BR
dc.subject.otherÁlgebra Linearpt_BR
dc.subject.otherTeoria dos Grafospt_BR
dc.titleColouring the Normalized Laplacianpt_BR
dc.title.alternativeColorindo o Laplaciano Normalizadopt_BR
dc.typeArtigo de Periódicopt_BR
dc.url.externahttps://www.sciencedirect.com/science/article/pii/S1571066119300817pt_BR
Aparece nas coleções:Artigo de Periódico

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Colouring the Normalized Laplacian.pdfA.pdf159.43 kBAdobe PDFVisualizar/Abrir
Mostrar registro simples do item Visualizar estatísticas


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.