Jogos de coloração de grafos com dois turnos

Resumen

Diversos problemas práticos podem ser modelados como problemas combinatórios. Em geral, não é possível controlar todas as variáveis presentes na aplicação em questão. Tais variáveis podem se manifestar como adversidades, comprometendo a confiabilidade dos resultados dos modelos. Jogos combinatórios fornecem um arcabouço robusto para abordar essas situações. Nesse cenário, um jogador denominado “adversário” incorpora as adversidades, e o desfecho desse jogo pode ser interpretado como “o melhor resultado possível diante de todas as adversidades enfrentadas”. O jogo de coloração consiste em, dado um grafo G e um conjunto finito de cores C, dois jogadores, Alice e Bob, tomam turnos colorindo os vértices de G, de forma que no término de cada jogada a coloração parcial resultante seja válida, isto é, que vértices adjacentes possuam cores distintas. O jogo termina quando não existem mais jogadas possíveis. Alice vence caso todos os vértices do grafo estejam coloridos e Bob vence caso contrário. O número cromático de jogo χg(G) é o menor número k de cores tal que Alice possui estratégia vencedora. Este jogo foi introduzido por Gardner como coloração de mapas, e formalizado por Bodlaender para grafos gerais. Consideraremos uma generalização apresentada em [3]. Na entrada, além de G e C, recebemos também dois inteiros não negativos a e b. Em vez de colorir apenas um vértice por turno, Alice e Bob tentam colorir respectivamente a e b vértices (ou os vértices restantes, caso não haja vértices suficientes). Este jogo ficou conhecido como jogo assimétrico de coloração, e de forma análoga à versão simétrica, temos o (a, b)−número cromático de jogo do grafo χg(G; a, b). Seja G um grafo, C um conjunto finito de cores e a, b ≤ |V (G)| inteiros não negativos, a notação para representar um jogo de dois turnos com estes parâmetros é (G; a, b, |C|). Tanto na versão simétrica quanto na versão assimétrica, a maior parte dos estudos na literatura focam em limitantes para o número cromático de jogo.