{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:04:21Z","timestamp":1740096261737,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642358425"},{"type":"electronic","value":"9783642358432"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-35843-2_26","type":"book-chapter","created":{"date-parts":[[2013,1,10]],"date-time":"2013-01-10T21:24:54Z","timestamp":1357853094000},"page":"292-306","source":"Crossref","is-referenced-by-count":1,"title":["Online and Quasi-online Colorings of Wedges and Intervals"],"prefix":"10.1007","author":[{"given":"Bal\u00e1zs","family":"Keszegh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathan","family":"Lemons","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00f6m\u00f6t\u00f6r","family":"P\u00e1lv\u00f6lgyi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Ajwani, D., Elbassioni, K., Govindarajan, S., Ray, S.: Conflict-Free Coloring for Rectangle Ranges Using \n                      \n                        \n                      \n                      $\\tilde{O}(n^{.382+\\epsilon})$\n                     Colors. In: Proceedings of the 19th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 181\u2013187 (2007)","DOI":"10.1145\/1248377.1248406"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Bar-Noy, A., Cheilaris, P., Smorodinsky, S.: Deterministic conflict-free coloring for intervals: From offline to online. ACM Transactions on Algorithms\u00a04(4) (2008)","DOI":"10.1145\/1383369.1383375"},{"key":"26_CR3","unstructured":"Cardinal, J., Cohen, N., Collette, S., Hoffmann, M., Rote, G: Coloring Dynamic Point Sets on a Line. In: EuroCG (2012)"},{"key":"26_CR4","unstructured":"Chen, X., Pach, J., Szegedy, M., Tardos, G.: Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pp. 94\u2013101 (2008)"},{"key":"26_CR5","first-page":"545","volume":"36","author":"K. Chen","year":"2006","unstructured":"Chen, K., Fiat, A., Levy, M., Matou\u0161ek, J., Mossel, E., Pach, J., Sharir, M., Smorodinsky, S., Wagner, U., Welzl, E.: Online conflict-free coloring for intervals, Siam. J. Comput.\u00a036, 545\u2013554 (2006)","journal-title":"J. Comput."},{"issue":"4","key":"26_CR6","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1051\/ita\/1988220404871","volume":"22","author":"M. Chrobak","year":"1988","unstructured":"Chrobak, M., Slusarek, M.: On some packing problems related to dynamic storage allocation. RAIRO Inform. Thor. Appl.\u00a022(4), 487\u2013499 (1988)","journal-title":"RAIRO Inform. Thor. Appl."},{"issue":"1","key":"26_CR7","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1137\/S0097539702431840","volume":"33","author":"G. Even","year":"2003","unstructured":"Even, G., Lotker, Z., Ron, D., Smorodinsky, S.: Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM J. Comput.\u00a033(1), 94\u2013136 (2003)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"26_CR8","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. Journal of Graph Theory\u00a012(2), 217\u2013227 (1988)","journal-title":"Journal of Graph Theory"},{"key":"26_CR9","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1016\/j.ipl.2010.03.001","volume":"110","author":"M.M. Halld\u00f3rsson","year":"2010","unstructured":"Halld\u00f3rsson, M.M.: Online Coloring of Hypergraphs. Information Processing Letters\u00a0110, 370\u2013372 (2010)","journal-title":"Information Processing Letters"},{"issue":"1","key":"26_CR10","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.ipl.2008.08.009","volume":"109","author":"J. Nagy-Gy\u00f6rgy","year":"2008","unstructured":"Nagy-Gy\u00f6rgy, J.: Cs. Imreh, Online hypergraph coloring. Information Processing Letters\u00a0109(1), 23\u201326 (2008)","journal-title":"Information Processing Letters"},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"Keszegh, B., P\u00e1lv\u00f6lgyi, D.: Octants are Cover Decomposable. Discrete and Computational Geometry (2011)","DOI":"10.1016\/j.endm.2011.09.081"},{"key":"26_CR12","unstructured":"Keszegh, B., P\u00e1lv\u00f6lgyi, D.: Octants are Cover Decomposable Into Many Coverings (manuscript)"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Keszegh, B.: Coloring half-planes and bottomless rectangles. Computational Geometry: Theory and Applications (2012), \n                      \n                        http:\/\/dx.doi.org\/10.1016\/j.comgeo.2011.09.004","DOI":"10.1016\/j.comgeo.2011.09.004"},{"key":"26_CR14","unstructured":"Keszegh, B.: Weak conflict free colorings of point sets and simple regions. In: Proceedings of the 19th Canadian Conference on Computational Geometry, pp. 97\u2013100 (2007)"},{"issue":"1","key":"26_CR15","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BF02780324","volume":"105","author":"H.A. Kierstead","year":"1996","unstructured":"Kierstead, H.A.: On-line coloring k-colorable graphs. Israel Journal of Mathematics\u00a0105(1), 93\u2013104 (1996)","journal-title":"Israel Journal of Mathematics"},{"issue":"4","key":"26_CR16","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1137\/0401048","volume":"1","author":"H.A. Kierstead","year":"1988","unstructured":"Kierstead, H.A.: The linearity of first-fit coloring of interval graphs. SIAM J. Discrete Math.\u00a01(4), 526\u2013530 (1988)","journal-title":"SIAM J. Discrete Math."},{"key":"26_CR17","unstructured":"Kierstead, H.A., Smith, D., Trotter, W.T.: First-fit coloring of interval graphs. In: SIAM Conference on Discrete Mathematics, Combinatorics and Partially Ordered Sets (2010)"},{"issue":"13","key":"26_CR18","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. Discrete Mathematics\u00a075(13), 319\u2013325 (1989)","journal-title":"Discrete Mathematics"},{"issue":"1","key":"26_CR19","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s11083-008-9076-6","volume":"25","author":"N.S. Narayanaswamy","year":"2008","unstructured":"Narayanaswamy, N.S., Babu, R.S.: A Note on First-Fit Coloring of Interval Graphs. Order\u00a025(1), 49\u201353 (2008)","journal-title":"Order"},{"key":"26_CR20","unstructured":"https:\/\/oeis.org\/A000930"},{"key":"26_CR21","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1007\/978-3-642-55566-4_30","volume-title":"Discrete and Computational Geometry - The Goodman-Pollack Festschrift","author":"J. Pach","year":"2003","unstructured":"Pach, J., T\u00f3th, G.: Conflict free colorings. In: Basu, S., et al. (eds.) Discrete and Computational Geometry - The Goodman-Pollack Festschrift, pp. 665\u2013671. Springer, Berlin (2003)"},{"key":"26_CR22","unstructured":"P\u00e1lv\u00f6lgyi, D.: Decomposition of Geometric Set Systems and Graphs, PhD thesis, arXiv:1009.4641[math.co]"},{"key":"26_CR23","unstructured":"Smorodinsky, S.: Conflict-Free Coloring and its Applications, arXiv:1005.3616v3 [math.co]"},{"issue":"3","key":"26_CR24","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/050642368","volume":"21","author":"S. Smorodinsky","year":"2007","unstructured":"Smorodinsky, S.: On The Chromatic Number of Some Geometric Hypergraphs. SIAM Journal on Discrete Mathematics\u00a021(3), 676\u2013687 (2007)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"26_CR25","doi-asserted-by":"crossref","unstructured":"Trotter, W.T.: New perspectives on interval orders and interval graphs. In: Bailey, R.A. (ed.) Surveys in Combinatorics. London Math. Soc. Lecture Note Ser, vol.\u00a0241, pp. 237\u2013286 (1997)","DOI":"10.1017\/CBO9780511662119.009"},{"key":"26_CR26","unstructured":"Tardos, G.: Personal Communication"},{"issue":"4","key":"26_CR27","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0020-0190(02)00283-1","volume":"84","author":"Y.-T. Tsaia","year":"2002","unstructured":"Tsaia, Y.-T., Lina, Y.-L., Hsu, F.R.: The on-line first-fit algorithm for radio frequency assignment problems. Information Processing Letters\u00a084(4), 195\u2013199 (2002)","journal-title":"Information Processing Letters"},{"key":"26_CR28","unstructured":"Woodall, D.R.: Problem No. 4, Combinatorics. In: McDonough, T.P., Marvon, V.C. (eds.) Proc. British Combin. Conf. 1973, Cambridge. London Math. Soc. Lecture Note Series, vol.\u00a013, p. 202 (1974)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2013: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-35843-2_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,10]],"date-time":"2019-05-10T08:40:27Z","timestamp":1557477627000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-35843-2_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642358425","9783642358432"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-35843-2_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}