Portal de Eventos Científicos da UTFPR (EVIN), XXVI Seminário de Iniciação Científica e Tecnológica da UTFPR

Tamanho da fonte: 
Coloração Total em Potências de Ciclos
Daniel Akira Mori, Sheila Morais de Almeida

Última alteração: 2021-10-18

Resumo


Uma coloração total em um grafo é uma atribuição de cores para seus vértices e arestas de forma que quaisquer dois elementos adjacentes tenham cores distintas. O Problema da Coloração Total é, dado um grafo G, determinar seu número cromático total,X′′(G), que é o menor número de cores para uma coloração total de G. Por definição, X′′(G)≥Δ(G)+1, onde Δ(G) é o maior número de arestas incidentes em um mesmo vértice de G. Quando X′′(G)=Δ(G)+1, o grafo é Tipo 1; quando X′′(G)=Δ(G)+2, o grafo é Tipo 2. A Conjectura da Coloração Total (TCC), que está em aberto desde 1965, diz que X′′(G)≤Δ(G)+2, para qualquer grafo simples G. Decidir se um grafo simples é Tipo 1 é um problema computacionalmente difícil (NP-completo). Campos provou em 2004 que a TCC vale para a k-ésima potência do ciclo C_n, denotada por C_n^k, quando n é par, e n e k são inteiros positivos. Neste trabalho, a técnica de Campos foi modificada e uma coloração total para um subgrafo gerador do C_n^k foi obtida. Considerando esta coloração e n com qualquer paridade, propriedades sobre as listas de cores usadas e disponíveis em cada vértice do grafo são provadas.


Palavras-chave


coloração total. potência de ciclo. número cromático total. teoria dos grafos.

Texto completo: PDF