2009-02-01

# Geometric spanners with small chromatic number

## Publication

### Publication

*Computational Geometry , Volume 42 - Issue 2 p. 134- 146*

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.

Additional Metadata | |
---|---|

Keywords | Computational geometry, Geometric graph, k-colorable graphs, Online algorithm, Paz graph, Spanners |

Persistent URL | dx.doi.org/10.1016/j.comgeo.2008.04.003 |

Journal | Computational Geometry |

Citation |
Bose, P, Carmi, P. (Paz), Couture, M. (Mathieu), Maheshwari, A, Smid, M, & Zeh, N. (Norbert). (2009). Geometric spanners with small chromatic number.
Computational Geometry, 42(2), 134–146. doi:10.1016/j.comgeo.2008.04.003 |