Online chromatic number is PSPACE-complete

DOI10.1007/s00224-017-9797-2zbMath1391.68039arXiv1604.05940OpenAlexW2964333552MaRDI QIDQ726097

Pavel Veselý, Martin Böhm

Publication date: 3 August 2018

Published in: Lecture Notes in Computer Science, Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

PSPACE-completenessonline coloringonline chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)

Related Items (2)

Adding isolated vertices makes some greedy online algorithms optimal ⋮ Online chromatic number is PSPACE-complete

Cites Work

• Unnamed Item
• Unnamed Item
• On the computational complexity and strategies of online Ramsey theory
• Online chromatic number is PSPACE-complete
• An on-line graph coloring algorithm with sublinear performance ratio
• On-line coloring \(k\)-colorable graphs
• Lower bounds for on-line graph coloring
• Online coloring known graphs
• On the Complexity of Chooser–Picker Positional Games
• Deciding the On-line Chromatic Number of a Graph with Pre-coloring Is PSPACE-Complete
• ON THE COMPLEXITY OF SOME COLORING GAMES
• Effective coloration
• Parallel and On-Line Graph Coloring

This page was built for publication: Online chromatic number is PSPACE-complete