20080827
Geometric spanners with small chromatic number
Publication
Publication
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, , 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 online 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, , , and give upper and lower bounds on t(k) for k∈>∈4.
Additional Metadata  

dx.doi.org/10.1007/9783540779186_7  
Organisation  School of Computer Science 
Bose, P, Carmi, P. (Paz), Couture, M. (Mathieu), Maheshwari, A, Smid, M, & Zeh, N. (Norbert). (2008). Geometric spanners with small chromatic number. doi:10.1007/9783540779186_7
