On the Chromatic Number of Intersection Graphs of Convex Sets in the Plane

  • Seog-Jin Kim
  • Alexandr Kostochka
  • Kittikorn Nakprasit

Abstract

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$.

Published
2004-08-19
Article Number
R52