Coloração de arestas para grafos críticos

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorZatesko, Leandro Miranda-
Autor(es): dc.contributorZatesko, Leandro Miranda-
Autor(es): dc.contributorGroshaus, Marina Esther-
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.creatorCunha, Thiago Henrique Frois Menon-
Data de aceite: dc.date.accessioned2025-08-29T13:00:19Z-
Data de disponibilização: dc.date.available2025-08-29T13:00:19Z-
Data de envio: dc.date.issued2025-04-17-
Data de envio: dc.date.issued2025-04-17-
Data de envio: dc.date.issued2023-12-04-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/36586-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/1105757-
Descrição: dc.descriptionThe edge coloring was extensively studied by Vizing in his articles from 1964 and 1965, where he proved very important results such as Vizing’s Theorem and the Adjacency Lemma. Vizing’s Theorem establishes that a graph is either Class 1 or Class 2, and the Adjacency Lemma provides a lower bound for the number of vertices of degree ∆ in the neighborhood of a vertex in a critical graph. The edge recoloring procedure proposed by Vizing was crucial for proving these results. In his thesis, Zatesko (2018) showed an extension of this recoloring procedure, allowing for the optimal coloring of more graphs than with Vizing’s recoloring procedure. This extension considers not only the degrees of the vertices in a graph but also the degrees of the vertices in the neighborhood of a vertex, using concepts such as vertices of the hard core. The objective of this work is to prove extensions to Vizing’s results and other results from the literature using the extended recoloring procedure. So far, this approach has proven to be promising. The results obtained and proven in this work have been peer-reviewed and presented in workshops in the field.-
Descrição: dc.descriptionA coloração de arestas foi amplamente estudada por Vizing nos seus artigos de 1964 e 1965, onde provou resultados muito importantes, como o Teorema de Vizing e o Lema de Adjacências. O Teorema de Vizing estabelece que um grafo é Classe 1 ou Classe 2, e o Lema de Adjacências, um limitante inferior para o número de vértices de grau ∆ na vizinhança de um vértice de um grafo crítico. O procedimento de recoloração de arestas proposto por Vizing foi fundamental para a prova desses resultados. Em sua tese, Zatesko (2018) mostrou uma extensão desse procedimento de recoloração, possibilitando colorir otimamente mais grafos do que com o procedimento de recoloração de Vizing. Essa extensão considera não apenas os graus dos vértices de um grafo, mas também os graus dos vértices da vizinhança de um vértice, utilizando conceitos como vértices do núcleo duro. O objetivo deste trabalho é provar extensões para os resultados de Vizing, e outros resultados da literatura usando o procedimento de recoloração estendido. Até o momento, essa abordagem têm se mostrado promissora. Os resultados obtidos e provados no presente trabalho foram revisados por pares e apresentados em workshops da área.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Tecnológica Federal do Paraná-
Publicador: dc.publisherCuritiba-
Publicador: dc.publisherBrasil-
Publicador: dc.publisherSistemas de Informação-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Direitos: dc.rightshttp://creativecommons.org/licenses/by/4.0/-
Palavras-chave: dc.subjectTeoria dos grafos-
Palavras-chave: dc.subjectHipergrafos - Coloração-
Palavras-chave: dc.subjectAlgoritmos de grafos-
Palavras-chave: dc.subjectGraph theory-
Palavras-chave: dc.subjectHypergraphs - Coloring-
Palavras-chave: dc.subjectGraph algorithms-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO-
Título: dc.titleColoração de arestas para grafos críticos-
Título: dc.titleGraph coloring for critical graphs-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.