Back to Search
Start Over
Disjointness graphs of short polygonal chains
- Publication Year :
- 2021
- Publisher :
- arXiv, 2021.
-
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 $��$-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) \emph{$2$-way infinite} polygonal chains of length $3$ is $��$-bounded: for every such graph $G$, we have $��(G)\le(��(G))^3+��(G).$<br />14 pages, 4 figures
- Subjects :
- FOS: Mathematics
Combinatorics (math.CO)
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi...........06c6f41d87bf1ba2b8c1bc2e03e61bd2
- Full Text :
- https://doi.org/10.48550/arxiv.2112.05991