Triangle-Free Geometric Intersection Graphs with Large Chromatic Number

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 in that is not an axis-aligned rectangle and for any positive integer produces a family of sets, each obtained by an independent horizontal and vertical scaling and translation of , such that no three sets in pairwise intersect and . This provides a negative answer to a question of Gyarfas 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.