PSPACE-hardness of two graph coloring games

DOI10.1016/j.entcs.2019.08.030OpenAlexW2978184958WikidataQ113317402 ScholiaQ113317402MaRDI QIDQ2132363

Rudini Menezes Sampaio, Victor Lage Pessoa, R. Soares, Eurinardo R. Costa

Publication date: 27 April 2022

Full work available at URL: https://doi.org/10.1016/j.entcs.2019.08.030

zbMATH Keywords

game chromatic numbergreedy coloringGrundy numbercoloring gamePSPACE-hardness

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Graph theory (05Cxx)

Related Items (3)

A connected version of the graph coloring game ⋮ The connected greedy coloring game ⋮ \textsf{PSPACE}-hardness of variants of the graph coloring game

Cites Work

• Unnamed Item
• Unnamed Item
• Asymmetric coloring games on incomparability graphs
• Partitioning extended \(P_4\)-laden graphs into cliques and stable sets
• The game chromatic number and the game colouring number of cactuses
• Complement reducible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• 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
• \(P_{4}\)-laden graphs: A new class of brittle graphs
• The game coloring number of planar graphs with a specific girth
• On the Grundy number of graphs with few \(P_4\)'s
• The game Grundy number of graphs
• The game coloring number of pseudo partial \(k\)-trees
• The game coloring number of planar graphs with a given girth
• Refined activation strategy for the marking game
• The game chromatic number of trees and forests
• Radius two trees specify χ‐bounded classes
• The game chromatic number of random graphs

This page was built for publication: PSPACE-hardness of two graph coloring games