Viabilidade de Adaptação do Algoritmo de Coloração de Arestas de Vizing para Coloração Total de potência de ciclo
Mayara Midori Omai; Sheila Morais de Almeida
doi:10.20906/CPS/SICITE2015-0129
Resumo
Uma coloração de arestas de um grafo G consiste na atribuição de cores para as arestas de G de forma que arestas que incidem em um mesmo vértice devem ter cores distintas. O menor número de cores com o qual se pode fazer uma coloração de arestas de um grafo G é chamado de índice cromático de G e denotado por X'(G). Por definição, sabe-se que para qualquer grafo simples, G, X'(G) é no mínimo Δ(G), onde Δ(G) é o maior dentre os graus dos vértices do grafo G. O conhecido Teorema de Vizing impõe que um limite superior bastante justo para o índice cromático de um grafo simples G: X'(G) é no máximo Δ(G)+1. A prova do Teorema de Vizing sugere um algoritmo que colore as arestas de qualquer grafo simples com Δ(G)+1 cores. Uma coloração total consiste na atribuição de cores tanto para arestas como para vértices de um grafo G, de forma que elementos (arestas ou vértices) adjacentes devem ter cores distintas. O menor número de cores com o qual se pode obter uma coloração total de um grafo simples G é chamado de número cromático total e denotado por X''(G). Sabe-se que X''(G) é no mínimo Δ(G)+1 e conjectura-se que exista um resultado parecido com o Teorema de Vizing para a coloração total, impondo que X''(G) seja no máximo Δ(G)+2. Neste relatório apresentamos os resultados obtidos a partir da tentativa de adaptação do Algoritmo de Vizing para criar uma coloração total para as potências de ciclo. Além disso, é apresentada uma técnica de coloração para as terceiras e quartas potências de ciclo, que permitiu determinar o número cromático total de qualquer grafo desse conjunto, tal trabalho foi apresentado no 6th Latin American Workshop on Cliques in Graphs e permitiu ampliar o que se sabia sobre o número cromático total das potências de ciclo. O último resultado conhecido até então datava de 2007, quando Campos e Mello provaram que X''(G) é no máximo Δ(G)+2, confirmando a conjectura, e determinaram o número cromático total das segundas potências de ciclo.
Palavras-chave: Grafos; Potência de ciclo; Coloração total