Palestra do grupo de pesquisa GOHaN

Apresentação

Para a Turma da Mônica decidir o dono da rua entre a Mônica e o Cebolinha, Cascão propôs um jogo molhado para eles, chamado Jogo de Coloração em grafos. Dado um grafo G e um conjunto C de inteiros (tintas), Mônica e Cebolinha colorem vértices alternadamente (começando por Mônica) usando tintas de C de modo que vértices adjacentes recebam cores diferentes. Magali propôs uma versão gulosa do problema: a cor/tinta a ser usada é sempre a menor possível. Em 1991 (28 anos atrás), Bodlaender deixou uma pergunta em aberto: Qual a complexidade do problema do Cascão? Nessa apresentação, mostramos que tanto o problema do Cascão como o da Magali são PSPACE-Completos. Apesar desse resultado negativo, Xaveco, um personagem secundário da Turma da Mônica, deixou uma pergunta secundária: Qual seria a complexidade desses problemas na classe dos grafos P4-esparsos? Nessa apresentação, mostramos que o problema guloso da Magali é polinomial; mais ainda, o número mínimo de cores é o tamanho da maior clique do grafo P4-esparso. Finalmente, Cebolinha deseja fazer um plano infalível: o que acontece se ele começar os jogos ao invés da Mônica? Ele conseguirá evitar as coelhadas do Sansão? Descubra você mesmo nessa incrível historinha nesta terça-feira às 19h30. Cartunistas: Ronan Soares, Victor Lage Pessoa, Eurinardo Costa e Rudini Sampaio.

Programação

Palestra: "Mônica e Cebolinha em: "o plano infalível do jogo de coloração""