Disjointness graphs of short polygonal chains.

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). [ABSTRACT FROM AUTHOR]