On the chromatic number of intersection graphs of convex sets in the plane (Q1883668): Difference between revisions

Summary: Let \(G\) be the intersection graph of a finite family of convex sets obtained by translations of a fixed convex set in the plane. We show that every such graph with clique number \(k\) is \((3k-3)\)-degenerate. This bound is sharp. As a consequence, we derive that \(G\) is \((3k-2)\)-colorable. We show also that the chromatic number of every intersection graph \(H\) of a family of homothetic copies of a fixed convex set in the plane with clique number \(k\) is at most \(6k-6\).