The complexity of two colouring games

DOI10.1007/s00453-022-01069-wOpenAlexW4285020995MaRDI QIDQ2696280

Melissa Huggan, Stephan Dominique Andres, Richard J. Nowakowski, François Dross, Fionn Mc Inerney

Publication date: 11 April 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-01069-w

zbMATH Keywords

NP-completePSPACE-completecombinatorial gamescoring gameorthogonal colouring gameorthogonal graph colouringstrictly matched involution

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Guaranteed scoring games
• Impartial coloring games
• Upper bounds on sets of orthogonal colorings of graphs
• Occupation games on graphs in which the second player takes almost all vertices
• The game chromatic number and the game colouring number of cactuses
• On the complexity of some two-person perfect-information games
• Orthogonal colorings of graphs
• The game coloring number of planar graphs
• Games with guaranteed scores and waiting moves
• \textsc{influence}: a partizan scoring game on graphs
• PSPACE-completeness of two graph coloring games
• The orthogonal colouring game
• Refined activation strategy for the marking game
• On a vertex-capturing game
• ON THE COMPLEXITY OF SOME COLORING GAMES
• Game chromatic number of outerplanar graphs
• A Graph-Grabbing Game
• The complexity of satisfiability problems
• The Map-Coloring Game
• The incidence game chromatic number
• The largest connected subgraph game