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

DOI10.1016/J.TCS.2022.01.030MaRDI QIDQ2078618zbMATH OpenOpenAlexFDO

Authors Thiago Marcilon, Rudini M. Sampaio, Carlos Vinícius G. C. Lima, N. Martins

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

\textsf{PSPACE}-hardnesscoloring gamegame chromatic number

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• PSPACE-hardness of two graph coloring games
• PSPACE-completeness of two graph coloring games
• PSPACE-Hardness of some combinatorial games
• Hardness of variants of the graph coloring game
• \textsf{PSPACE}-complete two-color planar placement games
• Narrowing the complexity gap for colouring \((C_{s},P_{t})\)-free graphs
• The complexity of coloring games on perfect graphs
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances

Cites work

• A bound for the game chromatic number of graphs
• A connected version of the graph coloring game
• Characterising and recognising game-perfect graphs
• Game chromatic number of Cartesian product graphs
• Games, puzzles, and computation
• scientific article; zbMATH DE number 139777 (Why is no real title available?)
• scientific article; zbMATH DE number 398953 (Why is no real title available?)
• On the complexity of some two-person perfect-information games
• PSPACE-hardness of two graph coloring games
• Radius two trees specify χ‐bounded classes
• Refined activation strategy for the marking game
• The game chromatic number and the game colouring number of cactuses
• The game chromatic number of random graphs
• The game chromatic number of trees and forests
• The game coloring number of planar graphs
• The game coloring number of planar graphs with a given girth
• The game coloring number of planar graphs with a specific girth
• The game coloring number of pseudo partial \(k\)-trees

Cited in

(7)

• Hardness of variants of the graph coloring game
• PSPACE-hardness of two graph coloring games
• The complexity of two colouring games
• The connected greedy coloring game
• The general position avoidance game and hardness of general position games
• Hardness of some variants of the graph coloring game
• The harmonious coloring game

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2078618)