Coloring Triangle-Free Rectangle Overlap Graphs with $$O(\log \log n)$$ O ( log log n ) Colors
Tomasz Krawczyk, Arkadiusz Pawlik, Bartosz Walczak · Discrete & Computational Geometry · 2014
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).