O Seminário de Combinatória continua as suas atividades de forma online. Agradecemos a oportunidade de receber a Eder Ferreira de Figueiredo, estudante do doutorado em ciência da computação da UFMG.
Emitiremos certificados de participação para Atividade Complementar. Basta colocar seu nome completo, instituição de origem, e e-mail no Chat ao final do seminário.
Não é necessária inscrição prévia.
Data: 20/08/2025
Horário: 1:00pm (Brasil)
Sala: https://meet.google.com/cde-osms-aqn
Palestrante: Eder Ferreira de Figueiredo
Título: Alguns resultados sobre jogos de coloração em grafos
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.
Contamos com sua presença.
Atenciosamente,
Organização do Seminário de Combinatória – IME-UFF