PSPACE-completeness of two graph coloring games

Autor:	Rudini Menezes Sampaio, Victor Lage Pessoa, Ronan Pardo Soares, Eurinardo Rodrigues Costa
Rok vydání:	2020
Předmět:	Computer Science::Computer Science and Game Theory TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Mathematics::Combinatorics General Computer Science ComputingMilieux_PERSONALCOMPUTING ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION Two-graph 0102 computer and information sciences 02 engineering and technology Computer Science::Computational Complexity 01 natural sciences Theoretical Computer Science Greedy coloring Combinatorics Computer Science::Discrete Mathematics 010201 computation theory & mathematics Grundy number Completeness (order theory) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Chromatic scale Graph coloring game MathematicsofComputing_DISCRETEMATHEMATICS Mathematics PSPACE
Zdroj:	Theoretical Computer Science. :36-45
ISSN:	0304-3975
Popis:	In 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 split graphs and several superclasses of cographs, extending a result of Havet and Zhu in 2013.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::e059d660ab7fa4c6576dc5abbff4f3f3 https://doi.org/10.1016/j.tcs.2020.03.022 Zobrazit plný text záznamu Full Text from ScienceDirect