Pach, János and Tardos, Gábor and Tóth, Géza (2022) Disjointness Graphs of Short Polygonal Chains. In: 38th International Symposium on Computational Geometry (SoCG 2022). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 56. ISBN 9783959772273
|
Text
10.4230_lipics.socg.2022.56.pdf Available under License Creative Commons Attribution. Download (647kB) | Preview |
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))3 + ?(G). © Jnos Pach, Gbor Tardos, and Gza Tth; licensed under Creative Commons License CC-BY 4.0
| Item Type: | Book Section |
|---|---|
| Additional Information: | Rényi Institute, Budapest, Hungary MIPT, Moscow, Russian Federation Conference code: 180757 Export Date: 16 February 2023 Correspondence Address: Pach, J.; Rényi InstituteHungary Correspondence Address: Tardos, G.; Rényi InstituteHungary Correspondence Address: Tóth, G.; Rényi InstituteHungary Funding details: European Research Council, ERC, Z 342-N31 Funding details: Ministry of Education and Science of the Russian Federation, Minobrnauka, 075-15-2019-1926, 810115, 882971, K-132696, SSN-135643 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, K-131529 Funding text 1: Funding János Pach: 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. Gábor Tardos: 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. Géza Tóth: Supported by National Research, Development and Innovation Office, NKFIH, K-131529 and ERC Advanced Grant “GeoScape,”. |
| Uncontrolled Keywords: | Graph theory; Chromatic number; Graph G; Clique number; Set system; Disjointness; Disjointness graph; Disjointness graph; Polygonal chains; chi-bounded; chi-bounded; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 17 Mar 2023 08:00 |
| Last Modified: | 05 Apr 2024 10:50 |
| URI: | https://real.mtak.hu/id/eprint/162327 |
Actions (login required)
 |
Edit Item |
