{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T00:16:50Z","timestamp":1768695410468,"version":"3.49.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2016,12,22]],"date-time":"2016-12-22T00:00:00Z","timestamp":1482364800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1007\/s00493-016-3414-x","type":"journal-article","created":{"date-parts":[[2016,12,22]],"date-time":"2016-12-22T06:32:33Z","timestamp":1482388353000},"page":"1139-1179","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["On-Line Approach to Off-Line Coloring Problems on Graphs with Geometric Representations"],"prefix":"10.1007","volume":"37","author":[{"given":"Tomasz","family":"Krawczyk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bartosz","family":"Walczak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,12,22]]},"reference":[{"key":"3414_CR1","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s00454-009-9143-9","volume":"41","author":"E. Ackerman","year":"2009","unstructured":"E. Ackerman: On the maximum number of edges in topological graphs with no four pairwise crossing edges, Discrete Comput. Geom. 41 (2009), 365\u2013375.","journal-title":"Discrete Comput. Geom."},{"key":"3414_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01196127","volume":"17","author":"P. K. Agarwal","year":"1997","unstructured":"P. K. Agarwal, B. Aronov, J. Pach, R. Pollack and M. Sharir: Quasiplanar graphs have a linear number of edges, Combinatorica 17 (1997), 1\u20139.","journal-title":"Combinatorica"},{"key":"3414_CR3","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0012-365X(95)00349-2","volume":"152","author":"A. A. Ageev","year":"1996","unstructured":"A. A. Ageev: A triangle-free circle graph with chromatic number 5, Discrete Math. 152 (1996), 295\u2013298.","journal-title":"Discrete Math."},{"key":"3414_CR4","doi-asserted-by":"publisher","first-page":"181","DOI":"10.7146\/math.scand.a-10607","volume":"8","author":"E. Asplund","year":"1960","unstructured":"E. Asplund and B. Gr\u00fcnbaum: On a colouring problem, Math. Scand. 8 (1960), 181\u2013188.","journal-title":"Math. Scand."},{"key":"3414_CR5","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1017\/S0022481200051549","volume":"41","author":"D. R. Bean","year":"1976","unstructured":"D. R. Bean: Effective coloration, J. Symb. Logic 41 (1976), 289\u2013560.","journal-title":"J. Symb. Logic"},{"key":"3414_CR6","volume-title":"On coloring problems of families of prototypes","author":"J. P. Burling","year":"1965","unstructured":"J. P. Burling: On coloring problems of families of prototypes, PhD thesis, University of Colorado, Boulder, 1965."},{"key":"3414_CR7","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1016\/j.endm.2007.07.072","volume":"29","author":"J. \u010cern\u00fd","year":"2007","unstructured":"J. \u010cern\u00fd: Coloring circle graphs, Electron. Notes Discrete Math. 29 (2007), 457\u2013461.","journal-title":"Electron. Notes Discrete Math."},{"key":"3414_CR8","doi-asserted-by":"crossref","first-page":"30","DOI":"10.37236\/4424","volume":"23","author":"J. Chalopin","year":"2016","unstructured":"J. Chalopin, L. Esperet, Zh. Li and P. Ossona de Mendez: Restricted frame graphs and a conjecture of Scott, Electron. J. Combin. 23 (2016), P1.30.","journal-title":"Electron. J. Combin."},{"key":"3414_CR9","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1016\/j.ipl.2007.07.004","volume":"104","author":"J. Enright","year":"2007","unstructured":"J. Enright and L. Stewart: Subtree filament graphs are subtree overlap graphs, Inform. Process. Lett. 104 (2007), 228\u2013232.","journal-title":"Inform. Process. Lett."},{"key":"3414_CR10","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0925-7721(02)00089-5","volume":"23","author":"T. Erlebach","year":"2002","unstructured":"T. Erlebach and J. Fiala: On-line coloring of geometric intersection graphs, Comput. Geom. 23 (2002), 243\u2013255.","journal-title":"Comput. Geom."},{"key":"3414_CR11","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/S0304-3975(96)00204-6","volume":"175","author":"S. Felsner","year":"1997","unstructured":"S. Felsner: On-line chain partitions of orders, Theor. Comput. Sci. 175 (1997), 283\u2013292.","journal-title":"Theor. Comput. Sci."},{"key":"3414_CR12","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1016\/j.ejc.2011.09.021","volume":"33","author":"J. Fox","year":"2012","unstructured":"J. Fox and J. Pach: Coloring Kk-free intersection graphs of geometric objects in the plane, European J. Combin. 33 (2012), 853\u2013866.","journal-title":"European J. Combin."},{"key":"3414_CR13","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1017\/S0963548313000412","volume":"23","author":"J. Fox","year":"2014","unstructured":"J. Fox and J. Pach: Applications of a new separator theorem for string graphs, Combin. Prob. Comput. 23 (2014), 66\u201374.","journal-title":"Combin. Prob. Comput."},{"key":"3414_CR14","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F. Gavril","year":"1974","unstructured":"F. Gavril: The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combin. Theory Ser. B 16 (1974), 47\u201356.","journal-title":"J. Combin. Theory Ser. B"},{"key":"3414_CR15","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0020-0190(00)00025-9","volume":"73","author":"F. Gavril","year":"2000","unstructured":"F. Gavril: Maximum weight independent sets and cliques in intersection graphs of filaments, Inform. Process. Lett. 73 (2000), 181\u2013188.","journal-title":"Inform. Process. Lett."},{"key":"3414_CR16","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0012-365X(83)90019-5","volume":"43","author":"M. C. Golumbic","year":"1983","unstructured":"M. C. Golumbic, D. Rotem and J. Urrutia: Comparability graphs and intersection graphs, Discrete Math. 43 (1983), 37\u201346.","journal-title":"Discrete Math."},{"key":"3414_CR17","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0012-365X(85)90044-5","volume":"55","author":"A. Gy\u00e1rf\u00e1s","year":"1985","unstructured":"A. Gy\u00e1rf\u00e1s: On the chromatic number of multiple interval graphs and overlap graphs, Discrete Math. 55 (1985), 161\u2013166. Corrigendum: Discrete Math. 62 (1986), 333.","journal-title":"Discrete Math."},{"key":"3414_CR18","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1002\/jgt.3190120212","volume":"12","author":"A. Gy\u00e1rf\u00e1s","year":"1988","unstructured":"A. Gy\u00e1rf\u00e1s and J. Lehel: On-line and first fit colorings of graphs, J. Graph Theory 12 (1988), 217\u2013227.","journal-title":"J. Graph Theory"},{"key":"3414_CR19","volume-title":"Schranken f\u00fcr F\u00e4rbungs- und Cliquen\u00fcberdeckungszahl geometrisch repr\u00e4sentierbarer Graphen","author":"C. Hendler","year":"1998","unstructured":"C. Hendler: Schranken f\u00fcr F\u00e4rbungs- und Cliquen\u00fcberdeckungszahl geometrisch repr\u00e4sentierbarer Graphen, Master\u2019s thesis, Freie Universit\u00e4t Berlin, 1998."},{"key":"3414_CR20","first-page":"143","volume-title":"3rd Southeastern International Conference on Combinatorics, Graph Theory, and Computing (CGTC 1981)","author":"H. A. Kierstead","year":"1981","unstructured":"H. A. Kierstead and W. T. Trotter: An extremal problem in recursive combinatorics, in: F. Hoffman (ed.), 3rd Southeastern International Conference on Combinatorics, Graph Theory, and Computing (CGTC 1981), vol. 33 of Congressus Numerantium, 143\u2013153, Utilitas Math. Pub., Winnipeg, 1981."},{"key":"3414_CR21","first-page":"204","volume":"10","author":"A. Kostochka","year":"1988","unstructured":"A. Kostochka: On upper bounds for the chromatic numbers of graphs, Trudy Inst. Mat. 10 (1988), 204\u2013226 (in Russian).","journal-title":"Trudy Inst. Mat."},{"key":"3414_CR22","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1090\/conm\/342\/06137","volume-title":"Towards a Theory of Geometric Graphs","author":"A. Kostochka","year":"2004","unstructured":"A. Kostochka: Coloring intersection graphs of geometric figures with a given clique number, in: J. Pach (ed.), Towards a Theory of Geometric Graphs, vol. 342 of Contemp. Math., 127\u2013138, AMS, Providence, 2004."},{"key":"3414_CR23","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0012-365X(96)00344-5","volume":"163","author":"A. Kostochka","year":"1997","unstructured":"A. Kostochka and J. Kratochv\u00edl: Covering and coloring polygon-circle graphs, Discrete Math. 163 (1997), 299\u2013305.","journal-title":"Discrete Math."},{"key":"3414_CR24","first-page":"399","volume-title":"Thirty Essays on Geometric Graph Theory","author":"A. Kostochka","year":"2012","unstructured":"A. Kostochka and K. Milans: Coloring clean and K4-free circle graphs, in: J. Pach (ed.), Thirty Essays on Geometric Graph Theory, 399\u2013414, Springer, New York, 2012."},{"key":"3414_CR25","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s00454-014-9640-3","volume":"53","author":"T. Krawczyk","year":"2015","unstructured":"T. Krawczyk, A. Pawlik and B. Walczak: Coloring triangle-free rectangle overlap graphs with O(log logn) colors, Discrete Comput. Geom. 53 (2015), 199\u2013220.","journal-title":"Discrete Comput. Geom."},{"key":"3414_CR26","first-page":"55","volume-title":"Selected Topics in Graph Theory","author":"L. Lov\u00e1sz","year":"1983","unstructured":"L. Lov\u00e1sz: Perfect graphs, in: L. W. Beineke and R. J. Wilson (eds.), Selected Topics in Graph Theory, vol. 2, 55\u201387, Academic Press, London, 1983."},{"key":"3414_CR27","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-540-32439-3_12","volume-title":"More Graphs, Sets and Numbers","author":"J. Pach","year":"2006","unstructured":"J. Pach, R. Radoi\u010di\u0107 and G. T\u00f3th: Relaxing planarity for topological graphs, in: E. Gy\u0151ri, Gy. O. H. Katona and L. Lov\u00e1sz (eds.), More Graphs, Sets and Numbers, vol. 15 of Bolyai Soc. Math. Stud., 285\u2013300, Springer, Berlin, 2006."},{"key":"3414_CR28","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF02086610","volume":"16","author":"J. Pach","year":"1996","unstructured":"J. Pach, F. Shahrokhi and M. Szegedy: Applications of the crossing number, Algorithmica 16 (1996), 111\u2013117.","journal-title":"Algorithmica"},{"key":"3414_CR29","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1007\/s00454-013-9534-9","volume":"50","author":"A. Pawlik","year":"2013","unstructured":"A. Pawlik, J. Kozik, T. Krawczyk, M. Laso\u0144, P. Micek, W. T. Trotter and B. Walczak: Triangle-free geometric intersection graphs with large chromatic number, Discrete Comput. Geom. 50 (2013), 714\u2013726.","journal-title":"Discrete Comput. Geom."},{"key":"3414_CR30","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.jctb.2013.11.001","volume":"105","author":"A. Pawlik","year":"2014","unstructured":"A. Pawlik, J. Kozik, T. Krawczyk, M. Laso\u0144, P. Micek, W. T. Trotter and B. Walczak: Triangle-free intersection graphs of line segments with large chromatic number, J. Combin. Theory Ser. B 105 (2014), 6\u201310.","journal-title":"J. Combin. Theory Ser. B"},{"key":"3414_CR31","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-540-74839-7_23","volume-title":"33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007)","author":"M. Pergel","year":"2007","unstructured":"M. Pergel: Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete, in: A. Brandst\u00e4dt, D. Kratsch and H. M\u00fcller (eds.), 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007), vol. 4769 of Lecture Notes Comput. Sci., 238\u2013247, Springer, Berlin, 2007."},{"key":"3414_CR32","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1145\/2582112.2582115","volume-title":"30th Annual Symposium on Computational Geometry (SoCG 2014)","author":"A. Rok","year":"2014","unstructured":"A. Rok and B. Walczak: Outerstring graphs are \u03c7-bounded, in: S.-W. Cheng and O. Devillers (eds.), 30th Annual Symposium on Computational Geometry (SoCG 2014), 136\u2013143, ACM, New York, 2014."},{"key":"3414_CR33","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D. D. Sleator","year":"1983","unstructured":"D. D. Sleator and R. E. Tarjan: A data structure for dynamic trees, J. Comput. System Sci. 26 (1983), 362\u2013391.","journal-title":"J. Comput. System Sci."},{"key":"3414_CR34","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.comgeo.2015.06.001","volume":"50","author":"A. Suk","year":"2015","unstructured":"A. Suk and B. Walczak: New bounds on the maximum number of edges in k-quasiplanar graphs, Comput. Geom. 50 (2015), 24\u201333.","journal-title":"Comput. Geom."},{"key":"3414_CR35","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/PL00009364","volume":"19","author":"P. Valtr","year":"1998","unstructured":"P. Valtr: On geometric graphs with no k pairwise parallel edges, Discrete Comput. Geom. 19 (1998), 461\u2013469.","journal-title":"Discrete Comput. Geom."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-016-3414-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-016-3414-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-016-3414-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,28]],"date-time":"2020-09-28T04:49:23Z","timestamp":1601268563000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-016-3414-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,22]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["3414"],"URL":"https:\/\/doi.org\/10.1007\/s00493-016-3414-x","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,22]]}}}