Hardness of some variants of the graph coloring game

Very recently, a long-standing open question proposed by Bodlaender in 1991 was answered: the graph coloring game is PSPACE-complete. In 2019, Andres and Lock proposed five variants of the graph coloring game and left open the question of PSPACE-hardness related to them. In this paper, we prove that...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-11
Main Authors: Marcilon, Thiago, Martins, Nicolas, Sampaio, Rudini
Format: Article
Language:English
Subjects:
Games
Graph coloring
Hardness
Questions
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Very recently, a long-standing open question proposed by Bodlaender in 1991 was answered: the graph coloring game is PSPACE-complete. In 2019, Andres and Lock proposed five variants of the graph coloring game and left open the question of PSPACE-hardness related to them. In this paper, we prove that these variants are PSPACE-complete for the graph coloring game and also for the greedy coloring game, even if the number of colors is the chromatic number. Finally, we also prove that a connected version of the graph coloring game, proposed by Charpentier et al. in 2019, is PSPACE-complete.
ISSN:2331-8422