Detalhes bibliográficos
| Ano de defesa: |
2023 |
| Autor(a) principal: |
Huaynoca, Paola Tatiana Pantoja |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Não Informado pela instituição
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
http://app.uff.br/riuff/handle/1/29814
|
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. |
