2013/01/31 by Tomasz Krawczyk, Arkadiusz Pawlik, Bartosz Walczak · 13 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Bounded function #Brooks' theorem #Chordal graph #Chromatic scale #Complete coloring #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Graph coloring #Indifference graph #Intersection (aeronautics) #Intersection graph #Rectangle #cs.CG #cs.DM #math.CO #msc:05C15 #msc:05C62
paper · pdf · doi:10.1007/s00454-014-9640-3
published in Discrete & Computational Geometry 53(1), 199-220 (Springer Science+Business Media) · Minor revision
openalex publication_date 2014/11/25 · arxiv created 2014/12/26 · arxiv updated 2014/12/30 · openalex created_date 2019/06/27 · openalex updated_date 2026/08/06
Recently, it was proved that triangle-free intersection graphs of n line segments in the plane can have chromatic number as large as Θ (log log n) . Essentially the same construction produces Θ (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 R2 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).