Deciding the On-line Chromatic Number of a Graph with Pre-coloring Is PSPACE-Complete

DOI10.1007/978-3-319-18173-8_23zbMath1459.68078arXiv1406.1623OpenAlexW644085075MaRDI QIDQ2947029

Christian Kudahl

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

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 (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