{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T05:40:28Z","timestamp":1761198028889,"version":"3.37.3"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T00:00:00Z","timestamp":1641513600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T00:00:00Z","timestamp":1641513600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,5]]},"DOI":"10.1007\/s00453-021-00920-w","type":"journal-article","created":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T13:02:53Z","timestamp":1641560573000},"page":"1232-1251","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Online Coloring and a New Type of Adversary for Online Graph Problems"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9043-0375","authenticated-orcid":false,"given":"Yaqiao","family":"Li","sequence":"first","affiliation":[]},{"given":"Vishnu V.","family":"Narayan","sequence":"additional","affiliation":[]},{"given":"Denis","family":"Pankratov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,7]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Albers, S., Schraink, S.: Tight bounds for online coloring of basic graph classes. Algorithmica pp. 1\u201324 (2020)","key":"920_CR1","DOI":"10.1007\/s00453-020-00759-7"},{"doi-asserted-by":"publisher","unstructured":"Barab\u00e1si, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509\u2013512 (1999). https:\/\/doi.org\/10.1126\/science.286.5439.509. https:\/\/science.sciencemag.org\/content\/286\/5439\/509","key":"920_CR2","DOI":"10.1126\/science.286.5439.509"},{"issue":"2","key":"920_CR3","doi-asserted-by":"publisher","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."},{"issue":"1","key":"920_CR4","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/s00453-013-9819-7","volume":"70","author":"MP Bianchi","year":"2014","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H.J., Hromkovi\u010d, J., Keller, L.: Online coloring of bipartite graphs with and without advice. Algorithmica 70(1), 92\u2013111 (2014)","journal-title":"Algorithmica"},{"doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science 209(1), 1\u201345 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(97)00228-4. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397597002284","key":"920_CR5","DOI":"10.1016\/S0304-3975(97)00228-4"},{"doi-asserted-by":"crossref","unstructured":"Gutowski, G., Kozik, J., Micek, P., Zhu, X.: Lower bounds for on-line graph colorings. In: International Symposium on Algorithms and Computation, pp. 507\u2013515. Springer, New York (2014)","key":"920_CR6","DOI":"10.1007\/978-3-319-13075-0_40"},{"issue":"2","key":"920_CR7","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1002\/jgt.3190120212","volume":"12","author":"A Gy\u00e1rf\u00e1s","year":"1988","unstructured":"Gy\u00e1rf\u00e1s, A., Lehel, J.: On-line and first fit colorings of graphs. J. Graph Theory 12(2), 217\u2013227 (1988)","journal-title":"J. Graph Theory"},{"issue":"1","key":"920_CR8","doi-asserted-by":"publisher","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. Theoret. Comput. Sci. 130(1), 163\u2013174 (1994)","journal-title":"Theoret. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Kierstead, H.A.: Coloring graphs on-line. In: Fiat, A., Woeginger, G. J. (eds.) Online Algorithms, pp. 281\u2013305. Springer, New York (1998)","key":"920_CR9","DOI":"10.1007\/BFb0029574"},{"issue":"1","key":"920_CR10","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BF02780324","volume":"105","author":"HA Kierstead","year":"1998","unstructured":"Kierstead, H.A.: On-line coloring k-colorable graphs. Israel J. Math. 105(1), 93\u2013104 (1998)","journal-title":"Israel J. Math."},{"issue":"1\u20133","key":"920_CR11","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0012-365X(89)90096-4","volume":"75","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. Discret. Math. 75(1\u20133), 319\u2013325 (1989)","journal-title":"Discret. Math."},{"key":"920_CR12","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: An Introduction","author":"M Newman","year":"2010","unstructured":"Newman, M.: Networks: An Introduction. Oxford University Press Inc, Oxford (2010)"},{"key":"920_CR13","volume-title":"Advice complexity of online graph problems","author":"BC Steffen","year":"2014","unstructured":"Steffen, B.C.: Advice complexity of online graph problems. ETH Zurich, Zurich (2014)"},{"issue":"4","key":"920_CR14","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1016\/0196-6774(92)90061-G","volume":"13","author":"S Vishwanathan","year":"1992","unstructured":"Vishwanathan, S.: Randomized online graph coloring. J. Algorithms 13(4), 657\u2013669 (1992)","journal-title":"J. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00920-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00920-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00920-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T05:03:09Z","timestamp":1651122189000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00920-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,7]]},"references-count":14,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["920"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00920-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,1,7]]},"assertion":[{"value":"9 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}