Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
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 Θ(log log n). Essentially the same construction produces Θ(loglogn)-chromatic triangle-free intersection graphs of a variety of other geometric shapes-those belonging to any class of compact arc-connected subsets of ℝ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(loglogn), improving on the previous bound of O(logn). 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(loglogn) colors using a combination of techniques from on-line algorithms (first-fit) and data structure design (heavy-light decomposition). © 2013 Springer-Verlag.