×

Online chromatic number is PSPACE-complete. (English) Zbl 1391.68038

Mäkinen, Veli (ed.) et al., Combinatorial algorithms. 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17–19, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-44542-7/pbk; 978-3-319-44543-4/ebook). Lecture Notes in Computer Science 9843, 16-28 (2016).
Summary: 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, since it sees only previously colored neighbors of \(v\). 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.
For the entire collection see [Zbl 1343.68012].

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C15 Coloring of graphs and hypergraphs
68W27 Online algorithms; streaming algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bean, D.R.: Effective coloration. J. Symbolic Logic 41(2), 469–480 (1976) · Zbl 0331.02025 · doi:10.2307/2272247
[2] Böhm, M., Veselý, P.: Online chromatic number is PSPACE-complete, arXiv preprint (2016). https://arxiv.org/abs/1604.05940 · Zbl 1391.68038
[3] Gyárfás, A., Lehel, J.: First fit and on-line chromatic number of families of graphs. Ars Combinatoria 29C, 168–176 (1990) · Zbl 0712.05026
[4] Gyárfás, A., Kiraly, Z., Lehel, J.: On-line graph coloring and finite basis problems. In: Combinatorics: Paul Erdos is Eighty, vol. 1, pp. 207–214 (1993) · Zbl 0791.05041
[5] Halldórsson, M.M.: Parallel and on-line graph coloring. J. Algorithms 23, 265–280 (1997) · Zbl 0873.68165 · doi:10.1006/jagm.1996.0836
[6] Halldórsson, M.M.: Online coloring known graphs. Electron. J. Combinatorics 7(1), R7 (2000) · Zbl 0940.05030
[7] Halldórsson, M.M., Szegedy, M.: Lower bounds for on-line graph coloring. Theor. Comput. Sci. 130(1), 163–174 (1994) · Zbl 0822.68081 · doi:10.1016/0304-3975(94)90157-0
[8] Kierstad, H.: On-line coloring k-colorable graphs. Israel J. Math. 105, 93–104 (1998) · Zbl 0908.05043 · doi:10.1007/BF02780324
[9] Kudahl, C.: On-line graph coloring. Master’s thesis, University of Southern Denmark (2013) · Zbl 1459.68078
[10] Kudahl, C.: Deciding the on-line chromatic number of a graph with pre-coloring is PSPACE-complete. In: Paschos, V.T., Widmayer, P. (eds.) CIAC 2015. LNCS, vol. 9079, pp. 313–324. Springer, Heidelberg (2015) · Zbl 1459.68078 · doi:10.1007/978-3-319-18173-8_23
[11] Lovász, L., Saks, M., Trotter, W.T.: An on-line graph coloring algorithm with sublinear performance ratio. Ann. Discrete Math. 43, 319–325 (1989) · Zbl 0679.05031 · doi:10.1016/S0167-5060(08)70584-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.