Pach, János and Tardos, Gábor and Tóth, Géza (2024) Disjointness graphs of short polygonal chains. JOURNAL OF COMBINATORIAL THEORY SERIES B, 164. pp. 29-43. ISSN 0095-8956
|
Text
1-s2.0-S0095895623000679-main.pdf Available under License Creative Commons Attribution. Download (420kB) | 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). © 2023 The Author(s)
| Item Type: | Article |
|---|---|
| Additional Information: | Export Date: 2 February 2024 CODEN: JCBTB Funding details: European Research Council, ERC, 882971 Funding details: Austrian Science Fund, FWF, 101054936, K-132696, SSN-135643, Z 342-N31 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, K-131529 Funding text 1: Supported by the National Research, Development and Innovation Office, NKFIH grant K-131529, ERC Advanced Grant “GeoScape,” No. 882971 and the Austrian Science Fund grant Z 342-N31.Supported by the ERC Advanced Grant “ERMiD” No. 101054936, the ERC advanced grant “GeoScape,” No. 882971, and the National Research, Development and Innovation Office, NKFIH grants K-132696, SSN-135643.Supported by National Research, Development and Innovation Office, NKFIH grant K-131529 and ERC Advanced Grant “GeoScape,” No. 882971. |
| Uncontrolled Keywords: | Intersection graph; Coloring number; χ-bounded; Disjointness graph; |
| 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: | 05 Apr 2024 10:51 |
| Last Modified: | 05 Apr 2024 10:51 |
| URI: | https://real.mtak.hu/id/eprint/191856 |
Actions (login required)
 |
Edit Item |
