{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T05:47:14Z","timestamp":1768715234865,"version":"3.49.0"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2017,7,15]],"date-time":"2017-07-15T00:00:00Z","timestamp":1500076800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100007543","name":"Grantov\u00e1 Agentura, Univerzita Karlova","doi-asserted-by":"publisher","award":["634217"],"award-info":[{"award-number":["634217"]}],"id":[{"id":"10.13039\/100007543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["17-09142S"],"award-info":[{"award-number":["17-09142S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s00224-017-9797-2","type":"journal-article","created":{"date-parts":[[2017,7,15]],"date-time":"2017-07-15T06:31:12Z","timestamp":1500100272000},"page":"1366-1391","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Chromatic Number is PSPACE-Complete"],"prefix":"10.1007","volume":"62","author":[{"given":"Martin","family":"B\u00f6hm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavel","family":"Vesel\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,15]]},"reference":[{"issue":"2","key":"9797_CR1","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1017\/S0022481200051549","volume":"41","author":"DR Bean","year":"1976","unstructured":"Bean, D.R.: Effective coloration. J. Symb. Log. 41(2), 469\u2013480 (1976)","journal-title":"J. Symb. Log."},{"key":"9797_CR2","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1142\/S0129054191000091","volume":"2.02","author":"H Bodlaender","year":"1991","unstructured":"Bodlaender, H.: On the complexity of some coloring games. Int. J. Found. Comput. Sci. 2.02, 133\u2013147 (1991)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9797_CR3","first-page":"16","volume-title":"Proceedings of 27th International Workshop on Combinatorial Algorithms (IWOCA 2016). LNCS 9843","author":"M B\u00f6hm","year":"2016","unstructured":"B\u00f6hm, M., Vesel\u00fd, P.: Online chromatic number is PSPACE-complete. In: Proceedings of 27th international workshop on combinatorial algorithms (IWOCA 2016). LNCS 9843, pp. 16\u201328 (2016)"},{"key":"9797_CR4","unstructured":"Csernenszky, A., Martin, R.R., Pluh\u00e1r, A.: On the complexity of Chooser-Picker positional games. arXiv: 1605.05430 (2016)"},{"key":"9797_CR5","first-page":"729","volume-title":"Proceedings of 8th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015), vol. 49","author":"P Dvo\u0159\u00e1k","year":"2015","unstructured":"Dvo\u0159\u00e1k, P., Valla, T.: On the computational complexity and strategies of online Ramsey theory. In: Proceedings of 8th European conference on combinatorics, graph theory and applications (EuroComb 2015), vol. 49, pp. 729\u2013736 (2015)"},{"key":"9797_CR6","first-page":"168","volume":"29C","author":"A Gy\u00e1rf\u00e1s","year":"1990","unstructured":"Gy\u00e1rf\u00e1s, A., Lehel, J.: First fit and on-line chromatic number of families of graphs. Ars Combinatoria 29C, 168\u2013176 (1990)","journal-title":"Ars Combinatoria"},{"key":"9797_CR7","first-page":"207","volume":"1","author":"A Gy\u00e1rf\u00e1s","year":"1993","unstructured":"Gy\u00e1rf\u00e1s, A., Kiraly, Z., Lehel, J.: On-line graph coloring and finite basis problems. Combinatorics: Paul Erdos is Eighty 1, 207\u2013214 (1993)","journal-title":"Combinatorics: Paul Erdos is Eighty"},{"key":"9797_CR8","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1006\/jagm.1996.0836","volume":"23","author":"MM Halld\u00f3rsson","year":"1997","unstructured":"Halld\u00f3rsson, M.M.: Parallel and on-line graph coloring. J. Algorithms 23, 265\u2013280 (1997)","journal-title":"J. Algorithms"},{"issue":"1","key":"9797_CR9","doi-asserted-by":"crossref","first-page":"R7","DOI":"10.37236\/1485","volume":"7","author":"MM Halld\u00f3rsson","year":"2000","unstructured":"Halld\u00f3rsson, M.M.: Online coloring known graphs. Electron. J. Comb. 7(1), R7 (2000)","journal-title":"Electron. J. Comb."},{"key":"9797_CR10","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0304-3975(94)90157-0","volume":"130.1","author":"MM Halld\u00f3rsson","year":"1994","unstructured":"Halld\u00f3rsson, M.M., Szegedy, M.: Lower bounds for on-line graph coloring. Theor. Comput. Sci. 130.1, 163\u2013174 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"9797_CR11","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/BF02780324","volume":"105","author":"H Kierstad","year":"1998","unstructured":"Kierstad, H.: On-line coloring k-colorable graphs. Israel J. Math. 105, 93\u2013104 (1998)","journal-title":"Israel J. Math."},{"key":"9797_CR12","unstructured":"Kudahl, C.: On-line graph coloring. Master\u2019s thesis, University of Southern Denmark (2013)"},{"key":"9797_CR13","first-page":"313","volume-title":"Proceedings of 9th International Conference on Algorithms and Complexity (CIAC 2015). LNCS 9079","author":"C Kudahl","year":"2015","unstructured":"Kudahl, C.: Deciding the On-line chromatic number of a graph with pre-coloring is PSPACE-complete. In: Proceedings of 9th international conference on algorithms and complexity (CIAC 2015). LNCS 9079. arXiv: 1406.1623 , pp. 313\u2013324 (2015)"},{"key":"9797_CR14","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/S0167-5060(08)70584-3","volume":"43","author":"L Lov\u00e1sz","year":"1989","unstructured":"Lov\u00e1sz, L., Saks, M., Trotter, W.T.: An on-line graph coloring algorithm with sublinear performance ratio. Ann. Discrete Math. 43, 319\u2013325 (1989)","journal-title":"Ann. Discrete Math."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9797-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9797-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9797-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,12]],"date-time":"2020-10-12T13:55:38Z","timestamp":1602510938000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9797-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,15]]},"references-count":14,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["9797"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9797-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7,15]]}}}