PSPACE-hardness of Two Graph Coloring Games

Abstract

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 several superclasses of cographs, extending a result of Havet and Zhu in 2013.