Geometric Spanners With Small Chromatic Number

Abstract

Given an integer $k\ge 2$, we consider the problem of computing the smallest real number $t(k)$ such that for each set $P$ of points in the plane, there exists a $t(k)$-spanner for $P$ that has chromatic number at most $k$. We prove that $t(2)=3$, $t(3)=2$, $t(4)=\sqrt{2}$, and give upper and lower bounds on $t(k)$ for $k>4$. We also show that for any $\hat{I}\mu >0$, there exists a $(1+\hat{I}\mu )t(k)$-spanner for $P$ that has $O(|P|)$ edges and chromatic number at most $k$. Finally, we consider an on-line variant of the problem where the points of $P$ are given one after another, and the color of a point must be assigned at the moment the point is given. In this setting, we prove that $t(2)=3$, $t(3)=1+\sqrt{3}$, $t(4)=1+\sqrt{2}$, and give upper and lower bounds on $t(k)$ for $k>4$.