{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T21:05:20Z","timestamp":1775163920767,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,11,16]],"date-time":"2023-11-16T00:00:00Z","timestamp":1700092800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,11,16]],"date-time":"2023-11-16T00:00:00Z","timestamp":1700092800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2015\/17\/D\/ST1\/00585"],"award-info":[{"award-number":["2015\/17\/D\/ST1\/00585"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2015\/17\/D\/ST1\/00585"],"award-info":[{"award-number":["2015\/17\/D\/ST1\/00585"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A <jats:italic>grounded L-graph<\/jats:italic> is the intersection graph of a collection of \u201cL\u201d shapes whose topmost points belong to a common horizontal line. We prove that every grounded L-graph with clique number <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c9<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> has chromatic number at most <jats:inline-formula><jats:alternatives><jats:tex-math>$$17\\omega ^4$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>17<\/mml:mn>\n                    <mml:msup>\n                      <mml:mi>\u03c9<\/mml:mi>\n                      <mml:mn>4<\/mml:mn>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This improves the doubly-exponential bound of McGuinness and generalizes the recent result that the class of circle graphs is polynomially <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\chi $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c7<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-bounded. We also survey <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\chi $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c7<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-boundedness problems for grounded geometric intersection graphs and give a high-level overview of recent techniques to obtain polynomial bounds.<\/jats:p>","DOI":"10.1007\/s00454-023-00592-z","type":"journal-article","created":{"date-parts":[[2023,11,16]],"date-time":"2023-11-16T20:03:51Z","timestamp":1700165031000},"page":"1523-1550","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Grounded L-Graphs Are Polynomially $$\\chi $$-Bounded"],"prefix":"10.1007","volume":"70","author":[{"given":"James","family":"Davies","sequence":"first","affiliation":[]},{"given":"Tomasz","family":"Krawczyk","sequence":"additional","affiliation":[]},{"given":"Rose","family":"McCarty","sequence":"additional","affiliation":[]},{"given":"Bartosz","family":"Walczak","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,11,16]]},"reference":[{"key":"592_CR1","doi-asserted-by":"publisher","first-page":"181","DOI":"10.7146\/math.scand.a-10607","volume":"8","author":"E Asplund","year":"1960","unstructured":"Asplund, E., Gr\u00fcnbaum, B.: On a coloring problem. Math. Scand. 8, 181\u2013188 (1960)","journal-title":"Math. Scand."},{"key":"592_CR2","doi-asserted-by":"crossref","unstructured":"Bria\u0144ski, M., Davies, J., Walczak, B.: Separating polynomial $$\\chi $$-boundedness from $$\\chi $$-boundedness. Combinatorica, in press. https:\/\/doi.org\/10.1007\/s00493-023-00054-3","DOI":"10.1007\/s00493-023-00054-3"},{"key":"592_CR3","doi-asserted-by":"crossref","unstructured":"Cabello, S., Jej\u010di\u010d, M.: Refining the hierarchies of classes of geometric intersection graphs. Electron. J. Comb. 24(1):P1.33 (2017)","DOI":"10.37236\/6040"},{"issue":"1","key":"592_CR4","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0095-8956(92)90003-G","volume":"56","author":"V Capoyleas","year":"1992","unstructured":"Capoyleas, V., Pach, J.: A Tur\u00e1n-type theorem on chords of a convex polygon. J. Comb. Theory Ser. B 56(1), 9\u201315 (1992)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"592_CR5","doi-asserted-by":"publisher","first-page":"273","DOI":"10.7155\/jgaa.00470","volume":"22","author":"J Cardinal","year":"2018","unstructured":"Cardinal, J., Felsner, S., Miltzow, T., Tompkins, C., Vogtenhuber, B.: Intersection graphs of rays and grounded segments. J. Graph Algorithms Appl. 22(2), 273\u2013295 (2018)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"592_CR6","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.dam.2015.08.019","volume":"216","author":"D Catanzaro","year":"2017","unstructured":"Catanzaro, D., Chaplick, S., Felsner, S., Halld\u00f3rsson, B.V., Halld\u00f3rsson, M.M., Hixon, T., Stacho, J.: Max point-tolerance graphs. Discrete Appl. Math. 216(1), 84\u201397 (2017)","journal-title":"Discrete Appl. Math."},{"key":"592_CR7","unstructured":"Chalermsook, P.: Coloring and maximum independent set of rectangles. In Leslie\u00a0Ann Goldberg, Klaus Jansen, R.\u00a0Ravi, and Jos\u00e9 D.\u00a0P. Rolim, editors, 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 15th International Workshop on Randomization and Computation (APPROX\/RANDOM 2011), volume 6845 of Lect. Notes Comput. Sci., pages 123\u2013134. Springer, Heidelberg, (2011)"},{"key":"592_CR8","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Walczak, B.: Coloring and maximum weight independent set of rectangles. In D\u00e1niel Marx, editor, 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pages 860\u2013868. SIAM, Philadelphia, (2021)","DOI":"10.1137\/1.9781611976465.54"},{"issue":"12","key":"592_CR9","first-page":"5121","volume":"150","author":"J Davies","year":"2022","unstructured":"Davies, J.: Improved bounds for colouring circle graphs. Proc. Am. Math. Soc. 150(12), 5121\u20135135 (2022)","journal-title":"Proc. Am. Math. Soc."},{"issue":"3","key":"592_CR10","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1112\/blms.12447","volume":"53","author":"J Davies","year":"2021","unstructured":"Davies, J., McCarty, R.: Circle graphs are quadratically $$\\chi $$-bounded. Bull. Lond. Math. Soc. 53(3), 673\u2013679 (2021)","journal-title":"Bull. Lond. Math. Soc."},{"key":"592_CR11","first-page":"463","volume":"2","author":"P Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463\u2013470 (1935)","journal-title":"Compos. Math."},{"key":"592_CR12","unstructured":"Esperet, L.: Graph Colorings, Flows and Perfect Matchings. Habilitation thesis, Universit\u00e9 Grenoble Alpes, (2017)"},{"issue":"1","key":"592_CR13","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1017\/S0963548313000412","volume":"23","author":"J Fox","year":"2014","unstructured":"Fox, J., Pach, J.: Applications of a new separator theorem for string graphs. Comb. Probab. Comput. 23(1), 66\u201374 (2014)","journal-title":"Comb. Probab. Comput."},{"issue":"5\u20136","key":"592_CR14","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0020-0190(00)00025-9","volume":"73","author":"F Gavril","year":"2000","unstructured":"Gavril, F.: Maximum weight independent sets and cliques in intersection graphs of filaments. Inf. Process. Lett. 73(5\u20136), 181\u2013188 (2000)","journal-title":"Inf. Process. Lett."},{"key":"592_CR15","doi-asserted-by":"crossref","unstructured":"Golumbic, M.\u00a0C.: Algorithmic Graph Theory and Perfect Graphs, volume\u00a057 of Annals of Discrete Mathematics, 2nd edition. North Holland, Amsterdam (2004)","DOI":"10.1016\/S0167-5060(04)80051-7"},{"issue":"2","key":"592_CR16","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":"Gy\u00e1rf\u00e1s, A.: On the chromatic number of multiple interval graphs and overlap graphs. Discrete Math. 55(2), 161\u2013166 (1985)","journal-title":"Discrete Math."},{"issue":"3\u20134","key":"592_CR17","first-page":"413","volume":"19","author":"A Gy\u00e1rf\u00e1s","year":"1987","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. Appl. Math. 19(3\u20134), 413\u2013441 (1987)","journal-title":"Appl. Math."},{"key":"592_CR18","unstructured":"Hendler, C.: Schranken f\u00fcr F\u00e4rbungs- und Cliquen\u00fcberdeckungszahl geometrisch repr\u00e4sentierbarer Graphen (Bounds for chromatic and clique cover number of geometrically representable graphs). Master\u2019s thesis, Freie Universit\u00e4t Berlin, (1998)"},{"key":"592_CR19","doi-asserted-by":"crossref","unstructured":"Jel\u00ednek, V., T\u00f6pfer, M.: On grounded L-graphs and their relatives. Electron. J. Comb. 26(3):P3.17 (2019)","DOI":"10.37236\/8096"},{"key":"592_CR20","unstructured":"Kostochka, A.: O\u00a0verkhnikh otsenkakh khromaticheskogo chisla grafov (On upper bounds for the chromatic number of graphs). In Vladimir\u00a0T. Dementyev, editor, Modeli i\u00a0metody optimizacii, volume\u00a010 of Trudy Institute of Mathematics, pp. 204\u2013226. Akad. Nauk SSSR SO, Novosibirsk (1988)"},{"key":"592_CR21","doi-asserted-by":"crossref","unstructured":"Kostochka, A.: Coloring intersection graphs of geometric figures with a given clique number. In J. Pach, editor, Towards a theory of geometric graphs, volume 342 of Contemporary Mathematics, pp. 127\u2013138. AMS, Providence (2004)","DOI":"10.1090\/conm\/342\/06137"},{"issue":"1\u20133","key":"592_CR22","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0012-365X(96)00344-5","volume":"163","author":"A Kostochka","year":"1997","unstructured":"Kostochka, A., Kratochv\u00edl, J.: Covering and coloring polygon-circle graphs. Discrete Math. 163(1\u20133), 299\u2013305 (1997)","journal-title":"Discrete Math."},{"issue":"1","key":"592_CR23","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s00454-014-9640-3","volume":"53","author":"T Krawczyk","year":"2015","unstructured":"Krawczyk, T., Pawlik, A., Walczak, B.: Coloring triangle-free rectangle overlap graphs with $$O(\\log \\log n)$$ colors. Discrete Comput. Geom. 53(1), 199\u2013220 (2015)","journal-title":"Discrete Comput. Geom."},{"issue":"6","key":"592_CR24","doi-asserted-by":"publisher","first-page":"1139","DOI":"10.1007\/s00493-016-3414-x","volume":"37","author":"T Krawczyk","year":"2017","unstructured":"Krawczyk, T., Walczak, B.: On-line approach to off-line coloring problems on graphs with geometric representations. Combinatorica 37(6), 1139\u20131179 (2017)","journal-title":"Combinatorica"},{"issue":"2","key":"592_CR25","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s00454-014-9614-5","volume":"52","author":"M Laso\u0144","year":"2014","unstructured":"Laso\u0144, M., Micek, P., Pawlik, A., Walczak, B.: Coloring intersection graphs of arc-connected sets in the plane. Discrete Comput. Geom. 52(2), 399\u2013415 (2014)","journal-title":"Discrete Comput. Geom."},{"issue":"1\u20133","key":"592_CR26","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0012-365X(95)00316-O","volume":"154","author":"S McGuinness","year":"1996","unstructured":"McGuinness, S.: On bounding the chromatic number of L-graphs. Discrete Math. 154(1\u20133), 179\u2013187 (1996)","journal-title":"Discrete Math."},{"issue":"4","key":"592_CR27","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/PL00007228","volume":"16","author":"S McGuinness","year":"2000","unstructured":"McGuinness, S.: Colouring arcwise connected sets in the plane I. Graphs Comb. 16(4), 429\u2013439 (2000)","journal-title":"Graphs Comb."},{"issue":"1","key":"592_CR28","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0012-365X(92)90688-C","volume":"108","author":"M Middendorf","year":"1992","unstructured":"Middendorf, M., Pfeiffer, F.: The max clique problem in classes of string-graphs. Discrete Math. 108(1), 365\u2013372 (1992)","journal-title":"Discrete Math."},{"issue":"3","key":"592_CR29","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1007\/s00454-013-9534-9","volume":"50","author":"A Pawlik","year":"2013","unstructured":"Pawlik, A., Kozik, J., Krawczyk, T., Laso\u0144, M., Micek, P., Trotter, W.T., Walczak, B.: Triangle-free geometric intersection graphs with large chromatic number. Discrete Comput. Geom. 50(3), 714\u2013726 (2013)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"592_CR30","doi-asserted-by":"publisher","first-page":"2181","DOI":"10.1137\/17M1157374","volume":"33","author":"A Rok","year":"2019","unstructured":"Rok, A., Walczak, B.: Outerstring graphs are $$\\chi $$-bounded. SIAM J. Discrete Math. 33(4), 2181\u20132199 (2019)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"592_CR31","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1002\/jgt.22601","volume":"95","author":"A Scott","year":"2020","unstructured":"Scott, A., Seymour, P.: A survey of $$\\chi $$-boundedness. J. Graph Theory 95(3), 473\u2013504 (2020)","journal-title":"J. Graph Theory"},{"issue":"4","key":"592_CR32","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s00493-014-2942-5","volume":"34","author":"A Suk","year":"2014","unstructured":"Suk, A.: Coloring intersection graphs of $$x$$-monotone curves in the plane. Combinatorica 34(4), 487\u2013505 (2014)","journal-title":"Combinatorica"},{"key":"592_CR33","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2023.103831","author":"B Walczak","year":"2023","unstructured":"Walczak, B.: Coloring triangle-free L-graphs with $$O(\\log \\log n)$$ colors. Eur. J. Comb. (2023). https:\/\/doi.org\/10.1016\/j.ejc.2023.103831","journal-title":"Eur. J. Comb."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00592-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00592-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00592-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,25]],"date-time":"2023-11-25T23:05:33Z","timestamp":1700953533000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00592-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,16]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["592"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00592-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,16]]},"assertion":[{"value":"13 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 August 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 September 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 November 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}