Coloring triangle-free rectangle overlap graphs with $O(\log \log n)$ colors

Abstract

Recently, it was proved that triangle-free intersection graphs of $n$ line segments in the plane can have chromatic number as large as $\Theta (\log \log n)$. Essentially the same construction produces $\Theta (\log \log n)$-chromatic triangle-free intersection graphs of a variety of other geometric shapes---those belonging to any class of compact arc-connected sets in ${\mathbb{R}}^2$ closed under horizontal scaling, vertical scaling, and translation, except for axis-parallel rectangles. We show that this construction is asymptotically optimal for intersection graphs of boundaries of axis-parallel rectangles, which can be alternatively described as overlap graphs of axis-parallel rectangles. That is, we prove that triangle-free rectangle overlap graphs have chromatic number $O(\log \log n)$, improving on the previous bound of $O(\log n)$. To this end, we exploit a relationship between off-line coloring of rectangle overlap graphs and on-line coloring of interval overlap graphs. Our coloring method decomposes the graph into a bounded number of subgraphs with a tree-like structure that "encodes" strategies of the adversary in the on-line coloring problem. Then, these subgraphs are colored with $O(\log \log n)$ colors using a combination of techniques from on-line algorithms (first-fit) and data structure design (heavy-light decomposition).

Minor revision

References in corpus (3)

• Triangle-free intersection graphs of line segments with large chromatic number
• Triangle-free geometric intersection graphs with large chromatic number
• Coloring intersection graphs of arc-connected sets in the plane

Cited by in corpus (5)

• On-line approach to off-line coloring problems on graphs with geometric representations
• Burling graphs revisited, part I: New characterizations
• Reuniting $\chi$-boundedness with polynomial $\chi$-boundedness
• Burling graphs revisited, part III: Applications to $\chi$-boundedness
• Coloring lines and Delaunay graphs with respect to boxes