Document Open Access Logo

Disjointness Graphs of Short Polygonal Chains

Authors János Pach, Gábor Tardos, Géza Tóth

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.56.pdf
  • Filesize: 0.61 MB
  • 12 pages

Document Identifiers

Author Details

János Pach
  • Rényi Institute, Budapest, Hungary
  • MIPT, Moscow, Russia
Gábor Tardos
  • Rényi Institute, Budapest, Hungary
  • MIPT, Moscow, Russia
Géza Tóth
  • Rényi Institute, Budapest, Hungary

Funding

  • Pach, János: Supported by the National Research, Development and Innovation Office (NKFIH) grant K-131529, ERC Advanced Grant "GeoScape," the Austrian Science Fund grant Z 342-N31, and by the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant No. 075-15-2019-1926.
  • Tardos, Gábor: Supported by the ERC Synergy Grant "Dynasnet" No. 810115, the ERC advanced grant "GeoSpace" No. 882971, the National Research, Development and Innovation Office - NKFIH projects K-132696 and SSN-135643.
  • Tóth, Géza: Supported by National Research, Development and Innovation Office, NKFIH, K-131529 and ERC Advanced Grant "GeoScape,".

Cite AsGet BibTex

János Pach, Gábor Tardos, and Géza Tóth. Disjointness Graphs of Short Polygonal Chains. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 56:1-56:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.56

Abstract

The disjointness graph of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph G of any system of segments in the plane is χ-bounded, that is, its chromatic number χ(G) is upper bounded by a function of its clique number ω(G). Here we show that this statement does not remain true for systems of polygonal chains of length 2. We also construct systems of polygonal chains of length 3 such that their disjointness graphs have arbitrarily large girth and chromatic number. In the opposite direction, we show that the class of disjointness graphs of (possibly self-intersecting) 2-way infinite polygonal chains of length 3 is χ-bounded: for every such graph G, we have χ(G) ≤ (ω(G))³+ω(G).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph coloring
Keywords
  • chi-bounded
  • disjointness graph

Metrics

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

References

  1. Edgar Asplund and Branko Grünbaum. On a coloring problem. Mathematica Scandinavica, 8(1):181-188, 1960. Google Scholar
  2. Prosenjit Bose, Hazel Everett, Sándor P Fekete, Michael E Houle, Anna Lubiw, Henk Meijer, Kathleen Romanik, Günter Rote, Thomas C Shermer, Sue Whitesides, et al. A visibility representation for graphs in three dimensions. In Graph Algorithms And Applications I, pages 103-118. World Scientific, 2002. Google Scholar
  3. James P. Burling. On coloring problems of families of prototypes. (PhD thesis), University of Colorado, Boulder, 1965. Google Scholar
  4. Parinya Chalermsook and Bartosz Walczak. Coloring and maximum weight independent set of rectangles. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 860-868. SIAM, 2021. Google Scholar
  5. James Davies. Box and segment intersection graphs with large girth and chromatic number. Advances in Combinatorics, 2021. Google Scholar
  6. James Davies, Tomasz Krawczyk, Rose McCarty, and Bartosz Walczak. Grounded l-graphs are polynomially chi-bounded. arXiv preprint, 2021. URL: http://arxiv.org/abs/2108.05611.
  7. Michelle Delcourt and Luke Postle. Reducing linear hadwiger’s conjecture to coloring small graphs. arXiv preprint, 2021. URL: http://arxiv.org/abs/2108.01633.
  8. Paul Erdős and András Hajnal. On chromatic number of infinite graphs, theory of graphs. In Proc. Colloq. Tihany, Hungary, pages 83-98, 1966. Google Scholar
  9. Paul Erdős and András Hajnal. On chromatic number of graphs and set-systems. Acta Math. Acad. Sci. Hungar, 17(61-99):1, 1966. Google Scholar
  10. Peter Frankl. A constructive lower bound for ramsey numbers. Ars Combinatoria, 3(297-302):28, 1977. Google Scholar
  11. Sylvain Gravier, Chınh T Hoang, and Frédéric Maffray. Coloring the hypergraph of maximal cliques of a graph with no long path. Discrete mathematics, 272(2-3):285-290, 2003. Google Scholar
  12. András Gyárfás. On ramsey covering-numbers. Infinite and Finite Sets, 2:801-816, 1975. Google Scholar
  13. 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
  14. András Gyárfás. Problems from the world surrounding perfect graphs. Applicationes Mathematicae, 19(3-4):413-441, 1987. Google Scholar
  15. András Gyárfás and Jenő Lehel. Hypergraph families with bounded edge cover or transversal number. Combinatorica, 3(3-4):351-358, 1983. Google Scholar
  16. András Gyárfás and Jenő Lehel. Covering and coloring problems for relatives of intervals. Discrete Mathematics, 55(2):167-180, 1985. Google Scholar
  17. Hugo Hadwiger. Über eine klassifikation der streckenkomplexe. Vierteljschr. Naturforsch. Ges. Zürich, 88(2):133-142, 1943. Google Scholar
  18. Navin Kashyap, Paul H Siegel, and Alexander Vardy. An application of ramsey theory to coding for the optical channel. SIAM Journal on Discrete Mathematics, 19(4):921-937, 2005. Google Scholar
  19. 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
  20. Manor Mendel and Assaf Naor. Ramsey partitions and proximity data structures. Journal of the European Mathematical Society, 9(2):253-275, 2007. Google Scholar
  21. Friedhelm Meyer auf der Heide and Avi Wigderson. The complexity of parallel sorting. SIAM Journal on Computing, 16(1):100-107, 1987. Google Scholar
  22. Burkhard Monien and Ewald Speckenmeyer. Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informatica, 22(1):115-123, 1985. Google Scholar
  23. 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.
  24. János Pach, Gábor Tardos, and Géza Tóth. Disjointness graphs of segments in the space. Combinatorics, Probability and Computing, 30(4):498-512, 2021. Google Scholar
  25. János Pach and István Tomon. On the chromatic number of disjointness graphs of curves. Journal of Combinatorial Theory, Series B, 144:167-190, 2020. Google Scholar
  26. 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
  27. Vera Rosta. Ramsey theory applications. The Electronic Journal of Combinatorics, 1000:DS13-Dec, 2004. Google Scholar
  28. Alex Scott and Paul Seymour. A survey of χ-boundedness. Journal of Graph Theory, 95(3):473-504, 2020. Google Scholar
  29. David P Sumner. Subtrees of a graph and chromatic number. The Theory and Applications of Graphs,(G. Chartrand, ed.), John Wiley & Sons, New York, 557:576, 1981. 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