Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/36586| Título: | Coloração de arestas para grafos críticos |
| Título(s) alternativo(s): | Graph coloring for critical graphs |
| Autor(es): | Cunha, Thiago Henrique Frois Menon |
| Orientador(es): | Zatesko, Leandro Miranda |
| Palavras-chave: | Teoria dos grafos Hipergrafos - Coloração Algoritmos de grafos Graph theory Hypergraphs - Coloring Graph algorithms |
| Data do documento: | 5-Dez-2023 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Curitiba |
| Citação: | CUNHA, Thiago Henrique Frois Menon. Coloração de arestas para grafos críticos. 2023. Trabalho de Conclusão de Curso (Bacharelado em Sistemas de Informação) - Universidade Tecnológica Federal do Paraná, Curitiba, 2023. |
| Resumo: | A 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. |
| Abstract: | The 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. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/36586 |
| Aparece nas coleções: | CT - Sistemas de Informação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| coloracaoarestasgrafoscriticos.pdf | 267,77 kB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
