Conflict-free coloring game

Resumo

Dado um grafo $ G $ com $n$ vértices e $k> 1$ cores diferentes, o jogo Conflict Free $k$-coloring é um jogo \textit{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\in V$, se a vizinhança $N[v]$ (resp. $N(v)$) estiver totalmente colorido, então existe $w\in N[v]$ (resp. $w\in N(v)$) tal que $c(w)\neq c(w') $ para todo $w'\in N[v]$ (resp. $w\in N(v)$). Uma coloração de um vértice $v$ é dita \textit {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.

Dados da obra

Tipo

Dissertação (mestrado)

Instituição

UFF

Ano

2023

Idioma

pt

Palavras-chave

Jogos combinatórios; Teoria dos grafos; coloração de vértices; coloração Conflict-Free; Jogo em educação matemática; Grafo

Handle

http://app.uff.br/riuff/handle/1/29814

Acesso

Texto completo na fonte

Fontes

BDTD/IBICT

Na Biblioteca desde

01/10/2026 · verificada em 03/10/2026