Triangle-free geometric intersection graphs with large chromatic number

Abstract

Several classical constructions illustrate the fact that the chromatic number of a graph can 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 ${\mathbb{R}}^2$ that is not an axis-aligned rectangle and for any positive integer $k$ produces a family $\mathcal{F}$ of sets, each obtained by an independent horizontal and vertical scaling and translation of $X$, such that no three sets in $\mathcal{F}$ pairwise intersect and $\chi (\mathcal{F})>k$. 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, and 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.

Small corrections, bibliography update

Cited by in corpus (13)

• Triangle-free intersection graphs of line segments with large chromatic number
• On graphs with no induced subdivision of $K_4$
• A Novel Quantum Visual Secret Sharing Scheme
• Privacy-Preserving Quantum Two-Party Geometric Intersection
• Coloring triangle-free rectangle overlap graphs with $O(\log \log n)$ colors
• On-line approach to off-line coloring problems on graphs with geometric representations
• Coloring intersection graphs of arc-connected sets in the plane
• Triangle-free geometric intersection graphs with no large independent sets
• Burling graphs revisited, part I: New characterizations
• Decomposition of multiple packings with subquadratic union complexity
• Note on the number of edges in families with linear union-complexity
• Thickness and Antithickness of Graphs
• Grounded L-graphs are polynomially $\chi$-bounded