Deciding the On-line Chromatic Number of a Graph with Pre-coloring Is PSPACE-Complete
From MaRDI portal
Publication:2947029
DOI10.1007/978-3-319-18173-8_23zbMath1459.68078arXiv1406.1623OpenAlexW644085075MaRDI QIDQ2947029
Publication date: 21 September 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1406.1623
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 (3)
Adding isolated vertices makes some greedy online algorithms optimal ⋮ Deciding the On-line Chromatic Number of a Graph with Pre-coloring Is PSPACE-Complete ⋮ Online chromatic number is PSPACE-complete
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Asymmetric coloring games on incomparability graphs
- The polynomial-time hierarchy
- On-line 3-chromatic graphs. II: Critical graphs
- Precoloring extension on unit interval graphs
- Deciding the On-line Chromatic Number of a Graph with Pre-coloring Is PSPACE-Complete
- ON THE COMPLEXITY OF SOME COLORING GAMES
- Graph colorings with local constraints -- a survey
This page was built for publication: Deciding the On-line Chromatic Number of a Graph with Pre-coloring Is PSPACE-Complete