Viabilidade de Adaptação do Algoritmo de Coloração de Arestas de Potências de Ciclo para a Coloração Total da Classe

Jônatas Trabuco Belotti; Sheila Morais de Almeida

doi:10.20906/CPS/SICITE2015-0848

Resumo

O número máximo de arestas que incidem em um único vértice de um grafo G é chamado de grau do grafo G e denotado por ∆(G). A coloração total de um grafo G é a atribuição de cores para as arestas e vértices de G de forma que vértices adjacentes tenham cores diferentes, arestas incidentes no mesmo vértice tenham cores diferentes entre si e diferentes da cor do vértice em que incidem. O menor número de cores que permite uma coloração total do grafo G é chamado de número cromático total de G e denotado por X''(G). Por definição, X''(G) é no mínimo ∆(G)+1. Uma conjectura famosa sobre o tema é a Conjectura da Coloração Total (TCC), que limita o número cromático total a ∆(G)+2. Caso a TCC seja verdadeira, todo grafo simples G pode ser classificado de acordo com X''(G): tipo 1, se X''(G) = ∆(G)+1; ou tipo 2, se X''(G) = ∆(G)+2. Um grafo simples é um grafo sem laços ou arestas múltiplas. Decidir se um grafo simples G é tipo 1, é um problema NP-Completo. Campos e Mello provaram que a TCC é verdadeira para todas as potências de ciclo e conjecturam que a k-ésima potência de ciclo é tipo 2 quando k > n/2 + 1 e n é ímpar, e tipo 1 caso contrário, onde n é o número de vértices do grafo. Este trabalho prova que a Conjectura de Campos e Mello é verdadeira para as terceiras potências de ciclo. Para tal foram estudadas duas técnicas: a coloração de arestas de potências de ciclo apresentada por Meidanis e a técnica de colagem utilizada por Campos e Mello para a coloração das segundas potências de ciclo. O resultado é um avanço no que se sabia sobre a coloração total de potências de ciclo desde 2007, quando apenas o número cromático total das segundas potências de ciclo era conhecido. Esse trabalho apresenta o número cromático total das terceiras potências de ciclo e fornece uma técnica que pode ser utilizada com sucesso para a determinação do número cromático total das quartas potências de ciclo, esses resultados foram apresentados no 6th Latin American Workshop on Cliques in Graphs.

Palavras-chave: Grafos; Potências de ciclo; Coloração total