{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T06:18:39Z","timestamp":1725862719359},"publisher-location":"Cham","reference-count":11,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319445427"},{"type":"electronic","value":"9783319445434"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-44543-4_2","type":"book-chapter","created":{"date-parts":[[2016,8,8]],"date-time":"2016-08-08T11:49:58Z","timestamp":1470656998000},"page":"16-28","source":"Crossref","is-referenced-by-count":0,"title":["Online Chromatic Number is PSPACE-Complete"],"prefix":"10.1007","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":[[2016,8,9]]},"reference":[{"issue":"2","key":"2_CR1","doi-asserted-by":"crossref","first-page":"469","DOI":"10.2307\/2272247","volume":"41","author":"DR Bean","year":"1976","unstructured":"Bean, D.R.: Effective coloration. J. Symbolic Logic 41(2), 469\u2013480 (1976)","journal-title":"J. Symbolic Logic"},{"key":"2_CR2","unstructured":"B\u00f6hm, M., Vesel\u00fd, P.: Online chromatic number is PSPACE-complete, arXiv preprint (2016). https:\/\/arxiv.org\/abs\/1604.05940"},{"key":"2_CR3","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":"2_CR4","unstructured":"Gy\u00e1rf\u00e1s, A., Kiraly, Z., Lehel, J.: On-line graph coloring and finite basis problems. In: Combinatorics: Paul Erdos is Eighty, vol. 1, pp. 207\u2013214 (1993)"},{"key":"2_CR5","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":"2_CR6","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. Combinatorics 7(1), R7 (2000)","journal-title":"Electron. J. Combinatorics"},{"issue":"1","key":"2_CR7","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0304-3975(94)90157-0","volume":"130","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":"2_CR8","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":"2_CR9","unstructured":"Kudahl, C.: On-line graph coloring. Master\u2019s thesis, University of Southern Denmark (2013)"},{"key":"2_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/978-3-319-18173-8_23","volume-title":"Algorithms and Complexity","author":"C Kudahl","year":"2015","unstructured":"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\u2013324. Springer, Heidelberg (2015)"},{"key":"2_CR11","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":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-44543-4_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,24]],"date-time":"2020-09-24T22:36:02Z","timestamp":1600986962000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-44543-4_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319445427","9783319445434"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-44543-4_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}