Online chromatic number is PSPACE-complete

DOI10.1007/978-3-319-44543-4_2zbMATH Open1391.68039arXiv1604.05940OpenAlexW2964333552MaRDI QIDQ726097FDOQ726097

Authors: Martin Böhm, Pavel Veselý 

Publication date: 3 August 2018

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

Abstract: In the online graph coloring problem, vertices from a graph G, known in advance, arrive in an online fashion and an algorithm must immediately assign a color to each incoming vertex v so that the revealed graph is properly colored. The exact location of v in the graph G is not known to the algorithm. The online chromatic number of G is the smallest number of colors such that some online algorithm is able to properly color G for any incoming order. We prove that computing the online chromatic number of a graph is PSPACE-complete.

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

Recommendations

• Online chromatic number is PSPACE-complete
• Deciding the on-line chromatic number of a graph with pre-coloring is PSPACE-complete
• On-line P-coloring of graphs
• Circumference, chromatic number and online coloring
• Online coloring of hypergraphs
• Automata, Languages and Programming
• On-Line Coloring and Recursive Graph Theory
• On-line coloring \(k\)-colorable graphs
• Tight bounds for online coloring of basic graph classes
• Tight bounds for online coloring of basic graph classes

zbMATH Keywords

PSPACE-completenessonline coloringonline chromatic number

Mathematics Subject Classification ID

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

Cites Work

• Parallel and On-Line Graph Coloring
• Effective coloration
• On-line coloring \(k\)-colorable graphs
• ON THE COMPLEXITY OF SOME COLORING GAMES
• On the computational complexity and strategies of online Ramsey theory
• An on-line graph coloring algorithm with sublinear performance ratio
• Lower bounds for on-line graph coloring
• On the complexity of chooser-picker positional games
• Title not available (Why is that?)
• Online coloring known graphs
• Deciding the On-line Chromatic Number of a Graph with Pre-coloring Is PSPACE-Complete
• Title not available (Why is that?)
• Online chromatic number is PSPACE-complete

Cited In (2)

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

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

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