Detalhes bibliográficos
| Ano de defesa: |
2019 |
| Autor(a) principal: |
Pessoa, Victor Lage |
| 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://www.repositorio.ufc.br/handle/riufc/43286
|
Resumo: |
We answer in this dissertation a question that remained unanswered for the last 28 years: the complexity of Bodlaender’s graph coloring game. The coloring game in a simple graph G is played by two players: Alice and Bob, each has the same set of colors C having k distinct colors. In alternating turns, each chooses a single not yet colored vertex from G and a color from C used to color such vertex in a way that adjacent vertices have distinct colors. Alice wins the game when all vertices from G are properly colored and Bob wins if at any moment there is a vertex which cannot be colored by any of the k colors from C . We also studied the complexity of a variant of the game called the greed coloring game and obtained the game Grundy number for graphs of the P4 -sparse class in such game. |
