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.

Published in:
Discrete & Computational Geometry, 50, 3, 714-726
New York, Springer

 Record created 2013-11-04, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)