Data: 04/11/2021, às 16:00 horas (GMT-3, horário de Brasília).
Título: Jogo de Coloração em Grafos e suas variantes
Palestrante: Rudini Sampaio (UFC)

Resumo: O jogo de coloração em grafos foi introduzido em 1981 por Brams na coluna "Mathematical Games" da Scientific American. Mas só em 1991, começou a ser conhecido pela comunidade científica quando Bodlaender o reinventou, obteve alguns resultados e deixou uma pergunta em aberto sobre a complexidade computacional desse problema. Nesse jogo, Alice e Bob colorem os vértices de um grafo usando um conjunto de cores, com Alice iniciando o jogo. Se o grafo é inteiramente colorido, Alice vence. Caso contrário, Bob vence. O objetivo é saber o número mínimo de cores tal que Alice tenha uma estratégia vencedora. Em 2019, outras variantes foram introduzidas, permitindo a Bob iniciar o jogo e/ou permitindo a um deles pular jogadas, bem como obrigando que a coloração seja gulosa e/ou conexa. Nessa apresentação, mostraremos alguns resultados interessantes sobre esse problema e suas variantes.