PSPACE-hardness of Two Graph Coloring Games

Página do item simplificado
dc.creatorCosta, Eurinardo
dc.creatorPessoa, Victor Lage
dc.creatorSampaio, Rudini
dc.creatorSoares, Ronan
dc.date.accessioned2021-09-16T17:59:02Z
dc.date.available2021-09-16T17:59:02Z
dc.date.issued2019-08-30
dc.description.abstractIn 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.pt_BR
dc.description.provenanceSubmitted by André Calsavara (andre.calsavara@biblioteca.ufla.br) on 2021-09-16T17:58:54Z No. of bitstreams: 2 ARTIGO_PSPACE-hardness of Two Graph Coloring Games.pdf: 249147 bytes, checksum: b971f7ae70da87c3101b39653c8d4f8e (MD5) license_rdf: 907 bytes, checksum: c07b6daef3dbee864bf87e6aa836cde2 (MD5)en
dc.description.provenanceApproved for entry into archive by André Calsavara (andre.calsavara@biblioteca.ufla.br) on 2021-09-16T17:59:02Z (GMT) No. of bitstreams: 2 ARTIGO_PSPACE-hardness of Two Graph Coloring Games.pdf: 249147 bytes, checksum: b971f7ae70da87c3101b39653c8d4f8e (MD5) license_rdf: 907 bytes, checksum: c07b6daef3dbee864bf87e6aa836cde2 (MD5)en
dc.description.provenanceMade available in DSpace on 2021-09-16T17:59:02Z (GMT). No. of bitstreams: 2 ARTIGO_PSPACE-hardness of Two Graph Coloring Games.pdf: 249147 bytes, checksum: b971f7ae70da87c3101b39653c8d4f8e (MD5) license_rdf: 907 bytes, checksum: c07b6daef3dbee864bf87e6aa836cde2 (MD5) Previous issue date: 2019-08-30en
dc.identifier.citationCOSTA, E. et al. PSPACE-hardness of Two Graph Coloring Games. Electronic Notes in Theoretical Computer Science, [S. l.], v. 346, p. 333-344, 30 Aug. 2019. DOI: 10.1016/j.entcs.2019.08.030.pt_BR
dc.identifier.urihttps://repositorio.ufla.br/handle/1/48147
dc.languageen_USpt_BR
dc.publisherElsevierpt_BR
dc.rightsAttribution 4.0 International*
dc.rightsAttribution 4.0 International
dc.rightsacesso abertopt_BR
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/*
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/
dc.sourceElectronic Notes in Theoretical Computer Sciencept_BR
dc.subjectColoring gamept_BR
dc.subjectGame chromatic numberpt_BR
dc.subjectGreedy coloringpt_BR
dc.subjectGrundy numberpt_BR
dc.subjectPSPACE-hardnesspt_BR
dc.subjectJogos de colorirpt_BR
dc.subjectNúmero cromático do jogopt_BR
dc.subjectNúmero Grundypt_BR
dc.titlePSPACE-hardness of Two Graph Coloring Gamespt_BR
dc.typeArtigopt_BR

Arquivos

Pacote original

Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
ARTIGO_PSPACE-hardness of Two Graph Coloring Games.pdf
Tamanho:
243.31 KB
Formato:
Adobe Portable Document Format
Descrição:
Baixar

Licença do pacote

Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
license.txt
Tamanho:
953 B
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

DCC - Artigos publicados em periódicos