O jogo da coloração total em ciclos

Abstract

Uma Coloração Total de um grafo é uma coloração em que elementos adjacentes possuem cores distintas, isto é, vértices adjacentes, arestas adjacentes e arestas que incidem em vértices pertencem a partições distintas. O menor número de cores para o qual um grafo G admite uma Coloração Total é chamado de número cromático total e é representado por χT (G). O jogo da coloração, concebido na década de 80, surgiu como uma tentativa alternativa de provar o Teorema das Quatro Cores. Neste jogo, é dado um número finito t de cores, e os dois jogadores, chamados na literatura de Alice e Bob, se alternam colorindo os vértices ainda não coloridos de um grafo. Enquanto o objetivo de Alice é colorir o grafo utilizando no máximo t cores, o objetivo de Bob é o de impedi-la. Alice ganha a partida quando o grafo é completamente colorido com no máximo t cores, caso contrário, Bob ganha. Propomos um estudo do jogo da Coloração Total sobre ciclos, partindo do conhecimento prévio do número cromático total para esta classe de grafos.