ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract For a setS of points in the plane, letd 1〉d 2〉... denote the different distances determined byS. Consider the graphG(S, k) whose vertices are the elements ofS, and two are joined by an edge iff their distance is at leastd k . It is proved that the chromatic number ofG(S, k) is at most 7 if |S|≥constk 2. IfS consists of the vertices of a convex polygon and |S|≥constk 2, then the chromatic number ofG(S, k) is at most 3. Both bounds are best possible. IfS consists of the vertices of a convex polygon thenG(S, k) has a vertex of degree at most 3k − 1. This implies that in this case the chromatic number ofG(S, k) is at most 3k. The best bound here is probably 2k+1, which is tight for the regular (2k+1)-gon.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02187746
Permalink
