{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T07:42:38Z","timestamp":1648971758350},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T00:00:00Z","timestamp":1604448000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The <jats:italic>disjointness graph G = G<\/jats:italic>(<jats:italic>\ud835\udcae<\/jats:italic>) of a set of segments <jats:italic>\ud835\udcae<\/jats:italic> in <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000504_inline3.png\" \/><jats:tex-math>${\\mathbb{R}^d}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000504_inline4.png\" \/><jats:tex-math>$$d \\ge 2$$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, is a graph whose vertex set is <jats:italic>\ud835\udcae<\/jats:italic> and two vertices are connected by an edge if and only if the corresponding segments are disjoint. We prove that the chromatic number of <jats:italic>G<\/jats:italic> satisfies <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000504_inline6.png\" \/><jats:tex-math>$\\chi (G) \\le {(\\omega (G))^4} + {(\\omega (G))^3}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where <jats:italic>\u03c9<\/jats:italic>(<jats:italic>G<\/jats:italic>) denotes the clique number of <jats:italic>G<\/jats:italic>. It follows that <jats:italic>\ud835\udcae<\/jats:italic> has \u03a9(<jats:italic>n<\/jats:italic><jats:sup>1\/5<\/jats:sup>) pairwise intersecting or pairwise disjoint elements. Stronger bounds are established for lines in space, instead of segments.<\/jats:p><jats:p>We show that computing <jats:italic>\u03c9<\/jats:italic>(<jats:italic>G<\/jats:italic>) and <jats:italic>\u03c7<\/jats:italic>(<jats:italic>G<\/jats:italic>) for disjointness graphs of lines in space are NP-hard tasks. However, we can design efficient algorithms to compute proper colourings of <jats:italic>G<\/jats:italic> in which the number of colours satisfies the above upper bounds. One cannot expect similar results for sets of continuous arcs, instead of segments, even in the plane. We construct families of arcs whose disjointness graphs are triangle-free (<jats:italic>\u03c9<\/jats:italic>(<jats:italic>G<\/jats:italic>) = 2), but whose chromatic numbers are arbitrarily large.<\/jats:p>","DOI":"10.1017\/s0963548320000504","type":"journal-article","created":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T09:24:08Z","timestamp":1604481848000},"page":"498-512","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Disjointness graphs of segments in the space"],"prefix":"10.1017","volume":"30","author":[{"given":"J\u00e1nos","family":"Pach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00e1bor","family":"Tardos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00e9za","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,11,4]]},"reference":[{"key":"S0963548320000504_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4"},{"key":"S0963548320000504_ref18","doi-asserted-by":"publisher","DOI":"10.4064\/am-19-3-4-413-441"},{"key":"S0963548320000504_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90094-X"},{"key":"S0963548320000504_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00344-5"},{"key":"S0963548320000504_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00158-3"},{"key":"S0963548320000504_ref24","doi-asserted-by":"publisher","DOI":"10.1137\/0210055"},{"key":"S0963548320000504_ref30","first-page":"85","article-title":"INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs","volume":"31","author":"Kratochv\u00edl","year":"1990","journal-title":"Comment. Math. Univ. Carolin."},{"key":"S0963548320000504_ref28","first-page":"127","author":"Kostochka","year":"2004"},{"key":"S0963548320000504_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9538-5"},{"key":"S0963548320000504_ref36","unstructured":"[36] M\u00fctze, T. , Walczak, B. and Wiechert, V. (2018) Realization of shift graphs as disjointness graphs of 1-intersecting curves in the plane. arXiv:1802.09969"},{"key":"S0963548320000504_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280661"},{"key":"S0963548320000504_ref35","volume-title":"Combinatorial Problems and Exercises","author":"Lov\u00e1sz","year":"1993"},{"key":"S0963548320000504_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"S0963548320000504_ref10","doi-asserted-by":"publisher","DOI":"10.2307\/1969503"},{"key":"S0963548320000504_ref27","first-page":"204","article-title":"Upper bounds for the chromatic numbers of graphs","volume":"10","author":"Kostochka","year":"1988","journal-title":"Trudy Inst. Mat. (Novosibirsk), Modeli i Metody Optim. (Russian)"},{"key":"S0963548320000504_ref39","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.11.001"},{"key":"S0963548320000504_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(72)90006-4"},{"key":"S0963548320000504_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.006"},{"key":"S0963548320000504_ref7","first-page":"14","article-title":"Ramsey-type theorems for lines in 3-space","volume":"18","author":"Cardinal","year":"2016","journal-title":"Discrete Math. Theoret. Comput. Sci."},{"key":"S0963548320000504_ref34","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90022-5"},{"key":"S0963548320000504_ref38","unstructured":"[38] Pach, J. and Tomon, I. (2019) On the chromatic number of disjointness graphs of curves. In 35th International Symposium on Computational Geometry (SoCG 2019), pp. 54.1\u201354.17. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik."},{"key":"S0963548320000504_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF03041066"},{"key":"S0963548320000504_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90045-7"},{"key":"S0963548320000504_ref37","unstructured":"[37] Norin, S. (2017) Problem session at the Geometric and Structural Graph Theory workshop, Banff, August 20\u201325, 2017."},{"key":"S0963548320000504_ref9","doi-asserted-by":"crossref","unstructured":"[9] Davies, J. and McCarty, R. (2019) Circle graphs are quadratically \u03c7-bounded. arXiv:1905.11578.","DOI":"10.1112\/blms.12447"},{"key":"S0963548320000504_ref13","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1028999083"},{"key":"S0963548320000504_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009317"},{"key":"S0963548320000504_ref40","first-page":"307","article-title":"A note on stable sets and colorings of graphs","volume":"15","author":"Poljak","year":"1974","journal-title":"Comment. Math. Univ. Carolin."},{"key":"S0963548320000504_ref2","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10607"},{"key":"S0963548320000504_ref32","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/26.2.132"},{"key":"S0963548320000504_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(76)90022-8"},{"key":"S0963548320000504_ref22","first-page":"65","article-title":"\u00dcber eine Art von Graphen","volume":"11","author":"Haj\u00f3s","year":"1957","journal-title":"Intern. Math. Nachr."},{"key":"S0963548320000504_ref3","unstructured":"[3] Berge, C. (1961) F\u00e4rbung von Graphen, deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind. Beitr\u00e4ge zur Graphentheorie (Vortr\u00e4ge w\u00e4hrend des graphentheoretischen Kolloquiums in Halle im M\u00e4rz 1960, German). Wiss. Zeitschr. Univ. Halle 10 114."},{"key":"S0963548320000504_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(86)90224-4"},{"key":"S0963548320000504_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579191"},{"key":"S0963548320000504_ref23","volume-title":"Geometry and the Imagination.","author":"Hilbert","year":"1952"},{"key":"S0963548320000504_ref5","unstructured":"[5] Burling, J. P. (1965) On coloring problems of families of prototypes. PhD thesis, University of Colorado, Boulder."},{"key":"S0963548320000504_ref21","first-page":"113","article-title":"\u00dcber die Aufl\u00f6sung von Graphen in vollst\u00e4ndige Teilgraphen (German)","volume":"1","author":"Hajnal","year":"1958","journal-title":"Ann. Univ. Sci. Budapest. E\u00f6tv\u00f6s. Sect. Math."},{"key":"S0963548320000504_ref8","unstructured":"[8] Chalermsook, P. and Walczak, B. (2019) Personal communication, Prague, September 2019."},{"key":"S0963548320000504_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02992776"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000504","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,10]],"date-time":"2021-06-10T14:35:24Z","timestamp":1623335724000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000504\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,4]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["S0963548320000504"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000504","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,4]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}