PSPACE-hardness of Two Graph Coloring Games

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.creatorCosta, Eurinardo-
Autor(es): dc.creatorPessoa, Victor Lage-
Autor(es): dc.creatorSampaio, Rudini-
Autor(es): dc.creatorSoares, Ronan-
Data de aceite: dc.date.accessioned2026-02-09T12:47:38Z-
Data de disponibilização: dc.date.available2026-02-09T12:47:38Z-
Data de envio: dc.date.issued2021-09-16-
Data de envio: dc.date.issued2021-09-16-
Data de envio: dc.date.issued2019-08-30-
Fonte completa do material: dc.identifierhttps://repositorio.ufla.br/handle/1/48147-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/1168398-
Descrição: dc.descriptionIn this paper, we answer a long-standing open question proposed by Bodlaender in 1991: the game chromatic number is PSPACE-hard. We also prove that the game Grundy number is PSPACE-hard. In fact, we prove that both problems (the graph coloring game and the greedy coloring game) are PSPACE-Complete even if the number of colors is the chromatic number. Despite this, we prove that the game Grundy number is equal to the chromatic number for several superclasses of cographs, extending a result of Havet and Zhu in 2013.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languageen-
Publicador: dc.publisherElsevier-
Direitos: dc.rightsAttribution 4.0 International-
Direitos: dc.rightsAttribution 4.0 International-
Direitos: dc.rightsacesso aberto-
Direitos: dc.rightshttp://creativecommons.org/licenses/by/4.0/-
Direitos: dc.rightshttp://creativecommons.org/licenses/by/4.0/-
???dc.source???: dc.sourceElectronic Notes in Theoretical Computer Science-
Palavras-chave: dc.subjectColoring game-
Palavras-chave: dc.subjectGame chromatic number-
Palavras-chave: dc.subjectGreedy coloring-
Palavras-chave: dc.subjectGrundy number-
Palavras-chave: dc.subjectPSPACE-hardness-
Palavras-chave: dc.subjectJogos de colorir-
Palavras-chave: dc.subjectNúmero cromático do jogo-
Palavras-chave: dc.subjectNúmero Grundy-
Título: dc.titlePSPACE-hardness of Two Graph Coloring Games-
Tipo de arquivo: dc.typeArtigo-
Aparece nas coleções:Repositório Institucional da Universidade Federal de Lavras (RIUFLA)

Não existem arquivos associados a este item.