{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T16:40:45Z","timestamp":1770741645737,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,8,25]],"date-time":"2020-08-25T00:00:00Z","timestamp":1598313600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,25]],"date-time":"2020-08-25T00:00:00Z","timestamp":1598313600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["691672"],"award-info":[{"award-number":["691672"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005713","name":"Technische Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005713","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We resolve a number of long-standing open problems in online graph coloring. More specifically, we develop tight lower bounds on the performance of online algorithms for fundamental graph classes. An important contribution is that our bounds also hold for randomized online algorithms, for which hardly any results were known. Technically, we construct lower bounds for chordal graphs. The constructions then allow us to derive results on the performance of randomized online algorithms for the following further graph classes: trees, planar, bipartite, inductive, bounded-treewidth and disk graphs. It shows that the best competitive ratio of both deterministic and randomized online algorithms is <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Theta (\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where <jats:italic>n<\/jats:italic> is the number of vertices of a graph. Furthermore, we prove that this guarantee cannot be improved if an online algorithm has a lookahead of size <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n\/\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> or access to a reordering buffer of size <jats:inline-formula><jats:alternatives><jats:tex-math>$$n^{1-\\epsilon }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:mo>-<\/mml:mo>\n                      <mml:mi>\u03f5<\/mml:mi>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, for any <jats:inline-formula><jats:alternatives><jats:tex-math>$$0&lt;\\epsilon \\le 1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>0<\/mml:mn>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mi>\u03f5<\/mml:mi>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. A consequence of our results is that, for all of the above mentioned graph classes except bipartite graphs, the natural <jats:italic>First Fit<\/jats:italic> coloring algorithm achieves an optimal performance, up to constant factors, among deterministic and randomized online algorithms.<\/jats:p>","DOI":"10.1007\/s00453-020-00759-7","type":"journal-article","created":{"date-parts":[[2020,8,25]],"date-time":"2020-08-25T11:03:37Z","timestamp":1598353417000},"page":"337-360","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Tight Bounds for Online Coloring of Basic Graph Classes"],"prefix":"10.1007","volume":"83","author":[{"given":"Susanne","family":"Albers","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Schraink","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,8,25]]},"reference":[{"key":"759_CR1","doi-asserted-by":"crossref","unstructured":"Avigdor-Elgrabli, N., Rabani, Y.: An optimal randomized online algorithm for reordering buffer management. In: Proceedings of 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201913), pp. 1\u201310 (2013)","DOI":"10.1109\/FOCS.2013.9"},{"issue":"4","key":"759_CR2","doi-asserted-by":"publisher","first-page":"35:1","DOI":"10.1145\/2663347","volume":"11","author":"N Avigdor-Elgrabli","year":"2015","unstructured":"Avigdor-Elgrabli, N., Rabani, Y.: An improved competitive algorithm for reordering buffer management. ACM Trans. Algorithms 11(4), 35:1\u201335:15 (2015)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"759_CR3","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1017\/S0963548309990587","volume":"19","author":"A Bar-Noy","year":"2010","unstructured":"Bar-Noy, A., Cheilaris, P., Olonetsky, S., Smorodinsky, S.: Online conflict-free colouring for hypergraphs. Comb. Probab. Comput. 19(4), 493\u2013516 (2010)","journal-title":"Comb. Probab. Comput."},{"issue":"4","key":"759_CR4","doi-asserted-by":"publisher","first-page":"44:1","DOI":"10.1145\/1383369.1383375","volume":"4","author":"A Bar-Noy","year":"2008","unstructured":"Bar-Noy, A., Cheilaris, P., Smorodinsky, S.: Deterministic conflict-free coloring for intervals: from offline to online. ACM Trans. Algorithms 4(4), 44:1\u201344:18 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"759_CR5","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1017\/S0022481200051549","volume":"41","author":"D Bean","year":"1976","unstructured":"Bean, D.: Effective coloration. J. Symb. Log. 41(2), 469\u2013480 (1976)","journal-title":"J. Symb. Log."},{"issue":"1","key":"759_CR6","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01294260","volume":"11","author":"S Ben-David","year":"1994","unstructured":"Ben-David, S., Borodin, A., Karp, R., Tardos, G., Wigderson, A.: On the power of randomization in on-line algorithms. Algorithmica 11(1), 2\u201314 (1994)","journal-title":"Algorithmica"},{"key":"759_CR7","unstructured":"Berge, C.: F\u00e4rbung von Graphen, deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind. Wiss. Z. Martin-Luther Univ. Halle-Wittenberg Math. Natur. Reihe 10(4), 114 (1961)"},{"issue":"1","key":"759_CR8","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., Hromkovic, J., Keller, L.: Online coloring of bipartite graphs with and without advice. Algorithmica 70(1), 92\u2013111 (2014)","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"759_CR9","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11(1\u20132), 1\u201321 (1993)","journal-title":"Acta Cybern."},{"issue":"11","key":"759_CR10","doi-asserted-by":"publisher","first-page":"3293","DOI":"10.1007\/s00453-017-0386-1","volume":"80","author":"J Boyar","year":"2018","unstructured":"Boyar, J., Epstein, L., Favrholdt, L.M., Larsen, K.S., Levin, A.: Batch coloring of graphs. Algorithmica 80(11), 3293\u20133315 (2018)","journal-title":"Algorithmica"},{"issue":"2","key":"759_CR11","doi-asserted-by":"publisher","first-page":"19:1","DOI":"10.1145\/3056461","volume":"50","author":"J Boyar","year":"2017","unstructured":"Boyar, J., Favrholdt, L.M., Kudahl, C., Larsen, K.S., Mikkelsen, J.W.: Online algorithms with advice: a survey. ACM Comput. Surv. 50(2), 19:1\u201319:34 (2017)","journal-title":"ACM Comput. Surv."},{"issue":"4","key":"759_CR12","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1142\/S0129054118410058","volume":"29","author":"E Burjons","year":"2018","unstructured":"Burjons, E., Hromkovic, J., Kr\u00e1lovic, R., Kr\u00e1lovic, R., Mu\u00f1oz, X., Unger, W.: Online graph coloring against a randomized adversary. Int. J. Found. Comput. Sci. 29(4), 551\u2013569 (2018)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"759_CR13","doi-asserted-by":"crossref","unstructured":"Burjons, E., Hromkovic, J., Mu\u00f1oz, X., Unger, W.: Online graph coloring with advice and randomized adversary. In: Proceedings of the 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM\u201916), pp. 229\u2013240. LNCS 9587, Springer (2016)","DOI":"10.1007\/978-3-662-49192-8_19"},{"issue":"2","key":"759_CR14","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1016\/j.tcs.2007.04.025","volume":"384","author":"I Caragiannis","year":"2007","unstructured":"Caragiannis, I., Fishkin, A.V., Kaklamanis, C., Papaioannou, E.: A tight bound for online colouring of disk graphs. Theoret. Comput. Sci. 384(2), 152\u2013160 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"759_CR15","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.jcss.2006.08.002","volume":"73","author":"RG Downey","year":"2007","unstructured":"Downey, R.G., McCartin, C.: Online promise problems with online width metrics. J. Comput. Syst. Sci. 73(1), 57\u201372 (2007)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"759_CR16","doi-asserted-by":"publisher","first-page":"1220","DOI":"10.1137\/130919738","volume":"43","author":"M Englert","year":"2014","unstructured":"Englert, M., \u00d6zmen, D., Westermann, M.: The power of reordering for online minimum makespan scheduling. SIAM J. Comput. 43(3), 1220\u20131237 (2014)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"759_CR17","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0925-7721(02)00089-5","volume":"23","author":"T Erlebach","year":"2002","unstructured":"Erlebach, T., Fiala, J.: On-line coloring of geometric intersection graphs. Comput. Geom. 23(2), 243\u2013255 (2002)","journal-title":"Comput. Geom."},{"key":"759_CR18","doi-asserted-by":"crossref","unstructured":"Erlebach, T., Fiala, J.: Independence and coloring problems on intersection graphs of disks. In: Bampis, E., Jansen, K., Kenyon, C. (eds.) Efficient Approximation and Online Algorithms: Recent Progress on Classical Combinatorial Optimization Problems and New Applications, pp. 135\u2013155. LNCS 3484, Springer (2006)","DOI":"10.1007\/11671541_5"},{"issue":"2\u20133","key":"759_CR19","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0012-365X(83)90154-1","volume":"43","author":"M Farber","year":"1983","unstructured":"Farber, M.: Characterizations of strongly chordal graphs. Discrete Math. 43(2\u20133), 173\u2013189 (1983)","journal-title":"Discrete Math."},{"issue":"2","key":"759_CR20","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":"2","key":"759_CR21","doi-asserted-by":"publisher","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(2), 265\u2013280 (1997)","journal-title":"J. Algorithms"},{"issue":"1","key":"759_CR22","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."},{"issue":"1","key":"759_CR23","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01294263","volume":"11","author":"S Irani","year":"1994","unstructured":"Irani, S.: Coloring inductive graphs on-line. Algorithmica 11(1), 53\u201372 (1994)","journal-title":"Algorithmica"},{"key":"759_CR24","doi-asserted-by":"crossref","unstructured":"Kierstead, H.A.: Coloring graphs on-line. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms, pp. 281\u2013305. LNCS 1442, Springer (1998)","DOI":"10.1007\/BFb0029574"},{"key":"759_CR25","first-page":"143","volume":"33","author":"HA Kierstead","year":"1981","unstructured":"Kierstead, H.A., Trotter, W.A.: An extremal problem in recursive combinatorics. Congres. Numer. 33, 143\u2013153 (1981)","journal-title":"Congres. Numer."},{"key":"759_CR26","doi-asserted-by":"crossref","unstructured":"Leonardi, S., Vitaletti, A.: Randomized lower bounds for online path coloring. In: Proceedings of the 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM\u201998), pp. 232\u2013247. LNCS 1518, Springer (1998)","DOI":"10.1007\/3-540-49543-6_19"},{"key":"759_CR27","doi-asserted-by":"publisher","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. Discret. Math. 43, 319\u2013325 (1989)","journal-title":"Ann. Discret. Math."},{"issue":"1\u20132","key":"759_CR28","first-page":"11","volume":"48","author":"D Marx","year":"2004","unstructured":"Marx, D.: Graph colouring problems and their applications in scheduling. Period. Polytech. Electr. Eng. 48(1\u20132), 11\u201316 (2004)","journal-title":"Period. Polytech. Electr. Eng."},{"key":"759_CR29","doi-asserted-by":"crossref","unstructured":"Narayanan, L.: Channel assignment and graph multicoloring. In: Handbook of Wireless Networks and Mobile Computing, pp. 71\u201394 (2004)","DOI":"10.1002\/0471224561.ch4"},{"issue":"2","key":"759_CR30","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"issue":"4","key":"759_CR31","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"},{"key":"759_CR32","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2001","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Pearson, London (2001)","edition":"2"},{"key":"759_CR33","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Probabilistic computations: toward a unified measure of complexity. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS\u201977), pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00759-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00759-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00759-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,24]],"date-time":"2021-08-24T23:44:11Z","timestamp":1629848651000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00759-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,25]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["759"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00759-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,25]]},"assertion":[{"value":"8 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}