\textsf{PSPACE}-hardness of variants of the graph coloring game

DOI10.1016/j.tcs.2022.01.030OpenAlexW4210788208MaRDI QIDQ2078618

Rudini Menezes Sampaio, Thiago Marcilon, Nícolas A. Martins, Carlos Vinícius G. C. Lima

Publication date: 1 March 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1911.10363

zbMATH Keywords

game chromatic numbercoloring game\textsf{PSPACE}-hardness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

The general position avoidance game and hardness of general position games ⋮ The connected greedy coloring game

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The game chromatic number and the game colouring number of cactuses
• On the complexity of some two-person perfect-information games
• A bound for the game chromatic number of graphs
• The game coloring number of planar graphs
• The game coloring number of planar graphs with a specific girth
• The game coloring number of pseudo partial \(k\)-trees
• The game coloring number of planar graphs with a given girth
• PSPACE-hardness of two graph coloring games
• A connected version of the graph coloring game
• Refined activation strategy for the marking game
• The game chromatic number of trees and forests
• Radius two trees specify χ‐bounded classes
• Characterising and recognising game-perfect graphs
• The game chromatic number of random graphs
• Game chromatic number of Cartesian product graphs

This page was built for publication: \textsf{PSPACE}-hardness of variants of the graph coloring game