Document Open Access Logo

On the Chromatic Number of Disjointness Graphs of Curves

Authors János Pach, István Tomon

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.54.pdf
  • Filesize: 0.51 MB
  • 17 pages

Document Identifiers

Author Details

János Pach
  • École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
  • Rényi Institute, Budapest, Hungary
István Tomon
  • École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland

Funding

  • Pach, János: Research partially supported by Swiss National Science Foundation grants no. 200020-162884 and 200021-175977.
  • Tomon, István: Research partially supported by Swiss National Science Foundation grants no. 200020-162884 and 200021-175977.

Acknowledgements

We would like to thank Andrew Suk, Gábor Tardos, Géza Tóth and Bartosz Walczak for fruitful discussions.

Cite AsGet BibTex

János Pach and István Tomon. On the Chromatic Number of Disjointness Graphs of Curves. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.54

Abstract

Let omega(G) and chi(G) denote the clique number and chromatic number of a graph G, respectively. The disjointness graph of a family of curves (continuous arcs in the plane) is the graph whose vertices correspond to the curves and in which two vertices are joined by an edge if and only if the corresponding curves are disjoint. A curve is called x-monotone if every vertical line intersects it in at most one point. An x-monotone curve is grounded if its left endpoint lies on the y-axis. We prove that if G is the disjointness graph of a family of grounded x-monotone curves such that omega(G)=k, then chi(G)<= binom{k+1}{2}. If we only require that every curve is x-monotone and intersects the y-axis, then we have chi(G)<= k+1/2 binom{k+2}{3}. Both of these bounds are best possible. The construction showing the tightness of the last result settles a 25 years old problem: it yields that there exist K_k-free disjointness graphs of x-monotone curves such that any proper coloring of them uses at least Omega(k^{4}) colors. This matches the upper bound up to a constant factor.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • string graph
  • chromatic number
  • intersection graph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Pankaj K Agarwal and Nabil H Mustafa. Independent set of intersection graphs of convex objects in 2D. Computational Geometry, 34(2):83-95, 2006. Google Scholar
  2. Edgar Asplund and Branko Grünbaum. On a coloring problem. Mathematica Scandinavica, 8(1):181-188, 1960. Google Scholar
  3. Peter Brass, William OJ Moser, and János Pach. Research problems in discrete geometry. Springer Science &Business Media, 2006. Google Scholar
  4. James Perkins Burling. On Coloring Problems of Families of Polytopes, 1965. Google Scholar
  5. Sergio Cabello, Jean Cardinal, and Stefan Langerman. The clique problem in ray intersection graphs. Discrete &computational geometry, 50(3):771-783, 2013. Google Scholar
  6. Márcia R Cerioli, Luerbio Faria, Talita O Ferreira, and Fábio Protti. On minimum clique partition and maximum independent set on unit disk graphs and penny graphs: complexity and approximation. Electronic Notes in Discrete Mathematics, 18:73-79, 2004. Google Scholar
  7. Robert P Dilworth. A decomposition theorem for partially ordered sets. Annals of mathematics, pages 161-166, 1950. Google Scholar
  8. Adrian Dumitrescu and János Pach. Minimum clique partition in unit disk graphs. In Graphs and Combinatorics, volume 27(3), pages 399-411. Springer, 2011. Google Scholar
  9. Stephan Eidenbenz and Christoph Stamm. Maximum clique and minimum clique partition in visibility graphs. In IFIP International Conference on Theoretical Computer Science, pages 200-212. Springer, 2000. Google Scholar
  10. Jacob Fox and János Pach. Computing the independence number of intersection graphs. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms, pages 1161-1165. Society for Industrial and Applied Mathematics, 2011. Google Scholar
  11. Zoltán Füredi. The maximum number of unit distances in a convex n-gon. J. Comb. Theory, Ser. A, 55(2):316-320, 1990. Google Scholar
  12. Michael R Garey and David S Johnson. Computers and intractability, volume 29. wh freeman New York, 2002. Google Scholar
  13. Fanika Gavril. Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks, 3(3):261-273, 1973. Google Scholar
  14. András Gyárfás. On the chromatic number of multiple interval graphs and overlap graphs. Discrete mathematics, 55(2):161-166, 1985. Google Scholar
  15. András Gyárfás. Problems from the world surrounding perfect graphs. Applicationes Mathematicae, 19(3-4):413-441, 1987. Google Scholar
  16. J Mark Keil and Lorna Stewart. Approximating the minimum clique cover and other hard problems in subtree filament graphs. Discrete Applied Mathematics, 154(14):1983-1995, 2006. Google Scholar
  17. Chaya Keller, Shakhar Smorodinsky, and Gábor Tardos. On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2254-2263. SIAM, 2017. Google Scholar
  18. Dániel Korándi and István Tomon. Improved Ramsey-type results in comparability graphs. arXiv preprint, 2018. URL: http://arxiv.org/abs/1810.00588.
  19. Alexandr Kostochka. Coloring intersection graphs of geometric figures with a given clique number. Contemporary mathematics, 342:127-138, 2004. Google Scholar
  20. Alexandr Kostochka and Jan Kratochvíl. Covering and coloring polygon-circle graphs. Discrete Mathematics, 163(1-3):299-305, 1997. Google Scholar
  21. Alexandr Kostochka and Jaroslav Nešetril. Chromatic number of geometric intersection graphs. In 1995 Prague Midsummer Combinatorial Workshop, volume 95(309), pages 43-45. KAM Series, 1995. Google Scholar
  22. Alexandr V Kostochka. Upper bounds on the chromatic number of graphs. Trudy Inst. Mat, 10:204-226, 1988. Google Scholar
  23. Jan Kratochvíl and Jirí Matousek. Intersection graphs of segments. Journal of Combinatorial Theory, Series B, 62(2):289-315, 1994. Google Scholar
  24. Jan Kratochvíl and Jaroslav Nešetřil. Independent set and clique problems in intersection-defined classes of graphs. Commentationes Mathematicae Universitatis Carolinae, 31(1):85-93, 1990. Google Scholar
  25. Jan Kynčl. Ramsey-type constructions for arrangements of segments. European Journal of Combinatorics, 33(3):336-339, 2012. Google Scholar
  26. David Larman, Jiří Matoušek, János Pach, and Jenő Törőcsik. A Ramsey-Type Result for Convex Sets. Bulletin of the London Mathematical Society, 26(2):132-136, 1994. Google Scholar
  27. Michał Lasoń, Piotr Micek, Arkadiusz Pawlik, and Bartosz Walczak. Coloring intersection graphs of arc-connected sets in the plane. Discrete &Computational Geometry, 52(2):399-415, 2014. Google Scholar
  28. Sean McGuinness. Colouring arcwise connected sets in the plane I. Graphs and Combinatorics, 16(4):429-439, 2000. Google Scholar
  29. Leon Mirsky. A dual of Dilworth’s decomposition theorem. The American Mathematical Monthly, 78(8):876-877, 1971. Google Scholar
  30. Torsten Mütze, Bartosz Walczak, and Veit Wiechert. Realization of shift graphs as disjointness graphs of 1-intersecting curves in the plane. arXiv preprint, 2018. URL: http://arxiv.org/abs/1802.09969.
  31. János Pach and Gábor Tardos. Forbidden paths and cycles in ordered graphs and matrices. Israel Journal of Mathematics, 155(1):359-380, 2006. Google Scholar
  32. János Pach, Gábor Tardos, and Géza Tóth. Disjointness graphs of segments. arXiv preprint, 2017. URL: http://arxiv.org/abs/1704.01892.
  33. János Pach and Jenő Törőcsik. Some geometric applications of Dilworth’s theorem. Discrete &Computational Geometry, 12(1):1-7, 1994. Google Scholar
  34. Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T Trotter, and Bartosz Walczak. Triangle-free intersection graphs of line segments with large chromatic number. Journal of Combinatorial Theory, Series B, 105:6-10, 2014. Google Scholar
  35. Alexandre Rok and Bartosz Walczak. Outerstring graphs are χ-bounded. In Symposium on Computational Geometry, page 136, 2014. Google Scholar
  36. Alexandre Rok and Bartosz Walczak. Coloring curves that cross a fixed curve. Discrete &Computational Geometry, pages 1-22, 2017. Google Scholar
  37. Andrew Suk. Coloring intersection graphs of x-monotone curves in the plane. Combinatorica, 34(4):487-505, 2014. Google Scholar
  38. Kenneth Jay Supowit. TOPICS IN COMPUTATIONAL GEOMETRY. UIUCDCS-R, 1982. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact