Dissertation Defense: Conflict-Free coloring game

M.Sc. Candidate: Paola Tatiana Pantoja Huaynoca

Thesis Committee: Simone Dantas de Souza (Advisor, UFF)
Miguel Alfredo del Rio Palma (UFR)
Telma Silveira Pará (FAETEC-RJ)

Date: 31 aug 2021, 16h.

Place: Google Meet: meet.google.com/qyv-aujk-brj

Abstract: Dado um grafo G com n vértices e k>1 cores diferentes, o jogo Conflict Free k-coloring é um jogo maker-breaker no qual dois jogadores, Alice e Bob, alternadamente se revezam atribuindo uma das k cores a cada vértice de um grafo G de modo que para cada v∈V, se a vizinhança N[v] (resp. N(V)) estiver totalmente colorida, então existe w∈N[v] (resp. w∈N(v)) tal que c(w)≠c(w') para todo w'∈N[v] (resp. w∈N(v)). Uma coloração de um vértice v é dita legal se, depois dela, em cada vizinhança totalmente colorida à qual v pertence, existe uma cor que aparece exatamente uma vez. Ambos os jogadores podem iniciar o jogo, jogam de forma otimizada e são obrigados a usar apenas colorações legais. Alice ganha se terminar com uma CF k-coloring de G, caso contrário, Bob ganha se

impedir que isso aconteça.
No presente trabalho, estudamos o Conflict Free k-coloring game em classes clássicas de grafos como grafos completos, caminhos, ciclos, grafos bipartidos completos e estrelas, fornecendo estratégias para
Bob e Alice ganharem o jogo.