The complexity of two colouring games

DOI10.1007/S00453-022-01069-WMaRDI QIDQ2696280zbMATH OpenOpenAlexFDO

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

Publication date 11 April 2023

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

combinatorial gameNP-completeorthogonal colouring gameorthogonal graph colouringPSPACE-completescoring gamestrictly matched involution

Mathematics Subject Classification ID

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

Recommendations

• The orthogonal colouring game
• scientific article; zbMATH DE number 139777
• ON THE COMPLEXITY OF SOME COLORING GAMES
• The complexity of coloring games on perfect graphs
• \textsf{PSPACE}-hardness of variants of the graph coloring game

Cites work

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

Cited in

(4)

• PSPACE-hardness of two graph coloring games
• The Parallel Complexity of Coloring Games
• Two graph-colouring games
• ON THE COMPLEXITY OF SOME COLORING GAMES

This page was built for publication: The complexity of two colouring games

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