{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:23:14Z","timestamp":1759335794412,"version":"build-2065373602"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T00:00:00Z","timestamp":1747440000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T00:00:00Z","timestamp":1747440000000},"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":["2019\/34\/E\/ST6\/00443","2019\/34\/E\/ST6\/00443"],"award-info":[{"award-number":["2019\/34\/E\/ST6\/00443","2019\/34\/E\/ST6\/00443"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.032.614","024.002.003","UMO-2018\/31\/G\/ST1\/03718"],"award-info":[{"award-number":["639.032.614","024.002.003","UMO-2018\/31\/G\/ST1\/03718"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-19-CE48-0013"],"award-info":[{"award-number":["ANR-19-CE48-0013"]}],"id":[{"id":"10.13039\/501100001665","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":[[2025,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Given a positive integer <jats:italic>d<\/jats:italic>, the class <jats:italic>d<\/jats:italic>-DIR is defined as all those intersection graphs formed from a finite collection of line segments in <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$${\\mathbb R}^2$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mi>R<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:msup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> having at most <jats:italic>d<\/jats:italic> slopes. Since each slope induces an interval graph, it easily follows for every <jats:italic>G<\/jats:italic> in <jats:italic>d<\/jats:italic>-DIR with clique number at most <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\omega $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c9<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> that the chromatic number <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\chi (G)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c7<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> of <jats:italic>G<\/jats:italic> is at most <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$d\\omega $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mi>\u03c9<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. We show for every even value of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\omega $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c9<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> how to construct a graph in <jats:italic>d<\/jats:italic>-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvo\u0159\u00e1k and Noorizadeh. Furthermore, we show that the <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\chi $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c7<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-binding function of <jats:italic>d<\/jats:italic>-DIR is <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\omega \\mapsto d\\omega $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c9<\/mml:mi>\n                    <mml:mo>\u21a6<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mi>\u03c9<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> for <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\omega $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c9<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> even and <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\omega \\mapsto d(\\omega -1)+1$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c9<\/mml:mi>\n                    <mml:mo>\u21a6<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>\u03c9<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> for <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\omega $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c9<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> odd. This extends an earlier result by Kostochka and Ne\u0161et\u0159il, which treated the special case <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$d=2$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00454-025-00737-2","type":"journal-article","created":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T14:37:25Z","timestamp":1747492645000},"page":"758-770","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The $$\\chi $$-Binding Function of d-Directional Segment Graphs"],"prefix":"10.1007","volume":"74","author":[{"given":"Lech","family":"Duraj","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4219-593X","authenticated-orcid":false,"given":"Ross J.","family":"Kang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hoang","family":"La","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan","family":"Narboni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Filip","family":"Pokr\u00fdvka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cl\u00e9ment","family":"Rambaud","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amadeus","family":"Reinald","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,17]]},"reference":[{"key":"737_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":"737_CR2","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Dvo\u0159\u00e1k, Z., Noorizadeh, F.: Chromatic number of intersection graphs of segments with two slopes. In: Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB23) (2023)","DOI":"10.5817\/CZ.MUNI.EUROCOMB23-018"},{"key":"737_CR3","unstructured":"Burling, J.P.: On coloring problems of families of polytopes. PhD thesis, University of Colorado, Boulder (1965)"},{"key":"737_CR4","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Walczak, B.: Coloring and maximum weight independent set of rectangles. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 860\u2013868. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2021)","DOI":"10.1137\/1.9781611976465.54"},{"key":"737_CR5","doi-asserted-by":"crossref","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. In: Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), vol.\u00a019, pp. 413\u2013441 (1988\/1987)","DOI":"10.4064\/am-19-3-4-413-441"},{"key":"737_CR6","unstructured":"Kostochka, A., Ne\u0161et\u0159il, J.: Chromatic number of geometric intersection graphs. In: Proceedings of the Prague Midsummer Combinatorial Workshop (Charles University, Prague), vol. 95\u2013309, pp. 43\u201345 (1995)"},{"issue":"1","key":"737_CR7","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/eujc.2000.0433","volume":"23","author":"AV Kostochka","year":"2002","unstructured":"Kostochka, A.V., Ne\u0161et\u0159il, J.: Colouring relatives of intervals on the plane. II: Intervals and rays in two directions. Eur. J. Comb. 23(1), 37\u201341 (2002)","journal-title":"Eur. J. Comb."},{"issue":"4","key":"737_CR8","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."},{"key":"737_CR9","unstructured":"McKee, T.A., McMorris, F.R.: Topics in intersection graph theory. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1999)"},{"key":"737_CR10","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.jctb.2013.11.001","volume":"105","author":"A Pawlik","year":"2014","unstructured":"Pawlik, A., Kozik, J., Krawczyk, T., Laso\u0144, M., Micek, P., Trotter, W.T., Walczak, B.: Triangle-free intersection graphs of line segments with large chromatic number. J. Comb. Theory Ser. B 105, 6\u201310 (2014)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"737_CR11","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"},{"key":"737_CR12","doi-asserted-by":"crossref","unstructured":"Spinrad, J.P.: Efficient graph representations. Fields Institute Monographs, vol. 19. American Mathematical Society, Providence, RI (2003)","DOI":"10.1090\/fim\/019"},{"issue":"4","key":"737_CR13","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"},{"issue":"1","key":"737_CR14","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s00454-014-9645-y","volume":"53","author":"B Walczak","year":"2015","unstructured":"Walczak, B.: Triangle-free geometric intersection graphs with no large independent sets. Discrete Comput. Geom. 53(1), 221\u2013225 (2015)","journal-title":"Discrete Comput. Geom."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00737-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-025-00737-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00737-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T07:58:27Z","timestamp":1759305507000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-025-00737-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,17]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["737"],"URL":"https:\/\/doi.org\/10.1007\/s00454-025-00737-2","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2025,5,17]]},"assertion":[{"value":"16 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 May 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2025","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This article was revised to add a missing author affiliation.","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}