ANÁLISE DO JOGO DA COLORAÇÃO GULOSA EM GRAFOS

XXXVII Encontro de Iniciação Científica

Diego Nogueira Feijo, Rudini Menezes Sampaio

Coloração em grafos é uma área bastante estudada dentro da matemática e computação, possuindo diversas subdivisões em estudo. Dentre elas, nós temos o jogo de coloração, onde duas pessoas, Alice e Bob, competem com as seguintes regras: Cada um colore um vértice do grafo com uma cor, alternadamente. Alice ganha se conseguir gerar uma coloração própria (vértices vizinhos com cores diferentes) com todos os vértices do grafo estando coloridos. Bob ganha se ocorrer o oposto, ou seja, se não for possível gerar a coloração que Alice deseja. Os estudos focam em achar o menor número de cores que permite Alice ganhar, sendo um problema de otimização. Este trabalho tem como foco o jogo da coloração gulosa, uma variação desse jogo, onde as cores possuem valor, e os jogadores devem sempre escolher a menor cor possível. A intenção do estudo era analisar um artigo sobre o assunto, entender seus resultados e possivelmente decidir futuros temas de estudo. No entanto, foram descobertos erros em algumas das provas de seus conceitos durante o processo de análise, na forma de contra-exemplos que não eram previstos nas descrições do artigo, o que necessitou devidas revisões e correções. Primeiramente, foi necessário checar se os resultados em si estavam equivocados ou se apenas as provas estavam pouco abrangentes. Como os resultados eram bem corroborados na literatura, a aproximação inicial foi corrigir as provas ou gerar alternativas. Comparar as provas problemáticas com as corretas foi uma forma de entender que aproximações usar para corrigi-las. Complementar as provas foi o suficiente para gerar a correção do artigo, não sendo necessárias novas provas ou revisão dos resultados. Assim, os resultados do artigo são coerentes. Além disso, foi feito um algoritmo para melhor entendimento do artigo e para explicitar melhor as correções realizadas. Por fim, agradecimentos ao meu orientador, Rudini Sampaio, e ao CNPq, pela oportunidade de exercer essa bolsa de iniciação científica.

Palavras-chave: Grafos. Jogo da Coloração. Coloração Gulosa. Computação.

Encontros Universitários da UFC, Fortaleza, v. 3, 2018

869