Name
Abstract | ||
|---|---|---|
The {\em 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 {\em $\chi$-bounded}, that is, its chromatic number $\chi(G)$ is upper bounded by a function of its clique number $\omega(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) \emph{$2$-way infinite} polygonal chains of length $3$ is $\chi$-bounded: for every such graph $G$, we have $\chi(G)\le(\omega(G))^3+\omega(G).$ |
Year | DOI | Venue |
|---|---|---|
2022 | 10.4230/LIPICS.SOCG.2022.56 | International Symposium on Computational Geometry (SoCG) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Pach | 1 | 2366 | 292.28 |
| Gábor Tardos | 2 | 1261 | 140.58 |
| Géza Tóth | 3 | 581 | 55.60 |