# Geometric spanners with small chromatic number

- Authors
- Journal
- Computational Geometry 0925-7721
- Publisher
- Elsevier
- Publication Date
- Volume
- 42
- Issue
- 2
- Identifiers
- DOI: 10.1016/j.comgeo.2008.04.003
- Keywords
- Disciplines

## Abstract

Abstract Given an integer k ⩾ 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 ) = 2 , and give upper and lower bounds on t ( k ) for k > 4 . We also show that for any ϵ > 0 , there exists a ( 1 + ϵ ) 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 + 3 , t ( 4 ) = 1 + 2 , and give upper and lower bounds on t ( k ) for k > 4 .

## There are no comments yet on this publication. Be the first to share your thoughts.