Recently, Pawlik et al. have shown that triangle-free intersection graphs of line segments in the plane can have arbitrarily large chromatic number. Specifically, they construct triangle-free segment intersection graphs with chromatic number direct-(log log n). Essentially the same construction produces direct-(log log n)-chromatic triangle-free intersection graphs of a variety of other geometric shapes-those belonging to any class of compact arc-connected subsets of R~2 closed under horizontal scaling, vertical scaling, and translation, except for axis-aligned rectangles. We show that this construction is asymptotically optimal for the class of rectangular frames (boundaries of axis-aligned rectangles). Namely, we prove that triangle-free intersection graphs of rectangular frames in the plane 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 rectangular frame intersection 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, and colors these subgraphs with O(log log n) colors using a combination of techniques from on-line algorithms (first-fit) and data structure design (heavy-light decomposition).
展开▼
