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

 

Abstract

An intersection graph of a family of convex sets is the graph whose vertex set is the family of convex sets and two vertices are adjacent if and only if they intersect. Let G be an intersection graph of a finite family of convex sets obtained by translations of a fixed convex set in the plane. We show that the chromatic number of G is at most 3k-2, where k is the clique number of G. Also we show that the chromatic number of an intersection graph H of convex sets obtained by translations and scalings of a fixed convex set in the plane is at most 6k-6, where k is the clique number of H.

This is joint work with Alexandr Kostochka and Kittikorn Nakprasit.