{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:50:02Z","timestamp":1760709002249,"version":"3.37.3"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,2,9]],"date-time":"2016-02-09T00:00:00Z","timestamp":1454976000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Polish National Science Center (PL)","award":["UMO-2011\/03\/D\/ST6\/01370"],"award-info":[{"award-number":["UMO-2011\/03\/D\/ST6\/01370"]}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft (DE)","doi-asserted-by":"publisher","award":["GRK 1408"],"award-info":[{"award-number":["GRK 1408"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00453-016-0130-2","type":"journal-article","created":{"date-parts":[[2016,2,9]],"date-time":"2016-02-09T10:39:24Z","timestamp":1455014364000},"page":"1060-1070","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["An On-line Competitive Algorithm for Coloring Bipartite Graphs Without Long Induced Paths"],"prefix":"10.1007","volume":"77","author":[{"given":"Piotr","family":"Micek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Veit","family":"Wiechert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,2,9]]},"reference":[{"issue":"2","key":"130_CR1","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/1240233.1240245","volume":"3","author":"J Boyar","year":"2007","unstructured":"Boyar, J., Favrholdt, L.M.: The relative worst order ratio for online algorithms. ACM Trans. Algorithms 3(2), 22 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"130_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1007\/11758471_28","volume-title":"Algorithms and Complexity","author":"HJ Broersma","year":"2006","unstructured":"Broersma, H.J., Capponi, A., Paulusma, D.: On-line coloring of $$H$$ H -free bipartite graphs. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) Algorithms and Complexity. Lecture Notes in Computer Science, vol. 3998, pp. 284\u2013295. Springer, Berlin (2006)"},{"issue":"1","key":"130_CR3","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1137\/060668675","volume":"22","author":"HJ Broersma","year":"2008","unstructured":"Broersma, H.J., Capponi, A., Paulusma, D.: A new algorithm for on-line coloring bipartite graphs. SIAM J. Discrete Math. 22(1), 72\u201391 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"130_CR4","doi-asserted-by":"crossref","unstructured":"Gutowski, G., Kozik, J., Micek, P.: Lower Bounds for On-line Graph Colorings. In 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15\u201317, 2014, Proceedings, volume 8889 of Lecture Notes in Computer Science, pp. 507\u2013515 (2014)","DOI":"10.1007\/978-3-319-13075-0_40"},{"key":"130_CR5","unstructured":"Gy\u00e1rf\u00e1s, A., Kir\u00e1ly, Z., Lehel, J.: On-line competitive coloring algorithms. Technical report TR-9703-1, available online at http:\/\/www.cs.elte.hu\/tr97\/tr9703-1.ps (1997)"},{"issue":"2","key":"130_CR6","doi-asserted-by":"crossref","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"},{"key":"130_CR7","unstructured":"Gy\u00e1rf\u00e1s, A., Lehel, J.: First fit and on-line chromatic number of families of graphs. Ars Combin. 29, 168\u2013176 (1990). Twelfth British Combinatorial Conference (Norwich, 1989)"},{"key":"130_CR8","first-page":"1233","volume-title":"Handbook of Recursive Mathematics","author":"HA Kierstead","year":"1998","unstructured":"Kierstead, H.A.: Recursive and on-line Graph Coloring. Handbook of Recursive Mathematics, vol. 2, pp. 1233\u20131269. North-Holland, Amsterdam (1998)"},{"issue":"1","key":"130_CR9","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1137\/S0895480192224737","volume":"7","author":"HA Kierstead","year":"1994","unstructured":"Kierstead, H.A., Penrice, S.G., Trotter, W.T.: On-line coloring and recursive graph theory. SIAM J. Discrete Math. 7(1), 72\u201389 (1994)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"130_CR10","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1137\/S0895480191218861","volume":"8","author":"HA Kierstead","year":"1995","unstructured":"Kierstead, H.A., Penrice, S.G., Trotter, W.T.: On-line and first-fit coloring of graphs that do not induce $$P_5$$ P 5 . SIAM J. Discrete Math. 8(4), 485\u2013498 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"130_CR11","unstructured":"Kierstead, HA., Trotter, WT.: An extremal problem in recursive combinatorics. In: Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. II, volume 33 of Congressus Numerantium, pp. 143\u2013153 (1981)"},{"issue":"1\u20133","key":"130_CR12","doi-asserted-by":"crossref","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.E., Trotter, W.T.: An on-line graph coloring algorithm with sublinear performance ratio. Discrete Math. 75(1\u20133), 319\u2013325 (1989)","journal-title":"Discrete Math."},{"key":"130_CR13","doi-asserted-by":"crossref","unstructured":"Micek, P., Wiechert, V.: An On-line Competitive Algorithm for Coloring $$P_8$$ P 8 -free Bipartite Graphs. In: 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15\u201317, 2014, Proceedings, volume 8889 of Lecture Notes in Computer Science, pp. 516\u2013527 (2014)","DOI":"10.1007\/978-3-319-13075-0_41"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0130-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0130-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0130-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0130-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,4]],"date-time":"2019-09-04T07:30:32Z","timestamp":1567582232000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0130-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,9]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["130"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0130-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,2,9]]}}}