voltarData: 20/08/2025
Título: Alguns resultados sobre jogos de coloração em grafos.
Palestrante: Eder Ferreira de Figueiredo, UFMG.
Data: 20 de agosto de 2025, 13 h.
Resumo: O jogo de coloração de grafos é um jogo de dois jogadores, Alice e Bob, definido sobre um grafo G e um conjunto de c cores. Começando por Alice, os jogadores alternam turnos escolhendo um vértice que ainda não foi colorido e atribuindo a esse vértice uma das cores de C, de forma que vértices vizinhos possuam cores diferentes. O jogo termina quando não existem mais jogadas válidas, e Alice vence se e somente se todos os vértices de G estiverem coloridos. O número cromático de jogo de G é o menor inteiro k tal que Alice possui estratégia vencedora no jogo de coloração de grafos jogado em G com k cores.Uma possível variação, chamada (a, b)-jogo de coloração, é uma versão assimétrica do jogo de coloração de grafos, onde em seus turnos Alice e Bob colorem (se possível) a e b vértices respectivamente. Um jogo de dois turnos, é uma instância de um (a, b)-jogo de coloração onde b = |V(G)| - a.
Para a versão simétrica, mostramos que se G é um grafo limiar como clique máxima de tamanho k, então o número cromático de jogo de G é no máximo 2k-3, e que se G é um grafo split com clique máxima de tamanho k, então o número cromático de jogo de G é no máximo 2k-1. Também mostramos que esses limites são justos.
Para jogos de dois turnos, caracterizamos os grafos em que Alice vence quando a=0 e a=1. Também exibimos um algoritmo de tempo polinomial para decidir se Alice possui estratégia vencedora no (k, |V(G)|- k)-jogo de coloração para um k fixo.
Obs: Vídeo.