2012/12/31 by Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk +4 · 35 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Chromatic scale #Clique #Combinatorics #Computational Geometry and Mesh Generation #Discrete mathematics #Equilateral triangle #Geometry #Graph #Homothetic transformation #Intersection (aeronautics) #Intersection graph #Limits and Structures in Graph Theory #Line graph #Line segment #Mathematics #Plane (geometry) #Rectangle #cs.CG #cs.DM #math.CO #msc:05C15 #msc:05C62
paper · pdf · doi:10.1007/s00454-013-9534-9
published in Discrete & Computational Geometry 50(3), 714-726 (Springer Science+Business Media) · Small corrections, bibliography update
openalex publication_date 2013/08/28 · arxiv created 2014/12/26 · arxiv updated 2014/12/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set X in ℝ2 that is not an axis-aligned rectangle and for any positive integer k produces a family F of sets, each obtained by an independent horizontal and vertical scaling and translation of X , such that no three sets in F pairwise intersect and χ (F )>k . This provides a negative answer to a question of Gyárfás and Lehel for L-shapes. With extra conditions we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries or equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.