## You are here

Homechromatic number of a metric space

## Primary tabs

# chromatic number of a metric space

The *chromatic number of a metric space* is the minimum number of
colors required to color the space in such a way that no two
points at distance $1$ are assigned the same color. Alternatively,
the chromatic number of a metric space is the
chromatic number of a graph whose
vertices are points of the space, and two points are connected by
an edge if they are at distance $1$ from each other.

For example, the chromatic number of $\mathbb{R}$ is $2$ because it is impossible to color $\mathbb{R}$ into one color, but it is possible to color $\mathbb{R}$ into $2$ colors by coloring each of the intervals $[k,k+1)$, where $k$ is an integer, red or blue according to whether $k$ is odd or even.

Unlike $\mathbb{R}$, the chromatic number of $\mathbb{R}^{n}$ is not known for any $n\geq 2$. For example, the chromatic number of the plane is known to be between $4$ and $7$ as the following pictures show.

0;<7pc,0pc>:<0pc,7pc>:: @=(-1.,0.),(0.,0.),(0.228714,0.973494),(-0.5,1.65831),(-1.22871,0.973494),(-0.271286,0.684819),(-0.728714,0.684819)@@*$\bullet$ \ar@-(-1.,0.);(0.,0.) \ar@-(0.,0.);(0.228714,0.973494) \ar@-(0.228714,0.973494);(-0.5,1.65831) \ar@-(-0.5,1.65831);(-1.22871,0.973494) \ar@-(-1.22871,0.973494);(-1.,0.) \ar@-(-1.,0.);(-0.271286,0.684819) \ar@-(-1.22871,0.973494);(-0.271286,0.684819) \ar@-(-0.5,1.65831);(-0.271286,0.684819) \ar@-(0.,0.);(-0.728714,0.684819) \ar@-(0.228714,0.973494);(-0.728714,0.684819) \ar@-(-0.5,1.65831);(-0.728714,0.684819) The Moser spindle. All edges are of unit length. The chromatic number is $4$.

\xy0;<1.8pc,1.039230484541326376pc>:<0pc,2.07846096908265275223293560980705pc>:: \xylattice-48-48 Periodic coloring of the plane with $7$ colors. The diameter of each hexagonal region is slightly less than $1$.

Using compactness argument one can show that if every finite set of points in the plane can be colored with $4$ colors, then the whole plane can be colored with $4$. However, if such a coloring exists, then at least one of the color sets is nonmeasurable with respect to the Lebesgue measure [3].

If the coloring of the plane is to consist of regions bounded by Jordan curves, then at least $6$ colors are needed [15]. Moreover, under the additional assumption that no two regions, which are distance less than $1$ apart, receive the same color, then at least $7$ colors are needed [14].

The following table summarizes known lower and upper bounds on the chromatic number of some metric spaces.

$\mathbb{R}^{2}$ | $\mathbb{R}^{3}$ | $\mathbb{R}^{4}$ | $\mathbb{R}^{5}$ | $\mathbb{R}^{6}$ | $\mathbb{R}^{7}$ | $\mathbb{R}^{n}$ | |
---|---|---|---|---|---|---|---|

Upper bound | 7 | 15[2, 8] | $(3+o(1))^{n}$[5] | ||||

Lower bound | 4 | 6[17] | 7[16] | 9[16] | 10[5] | 15[10] | $(1.239+o(1))^{n}$[10, 9] |

$\mathbb{Q}^{2}$ | $\mathbb{Q}^{3}$ | $\mathbb{Q}^{4}$ | $\mathbb{Q}^{5}$ | $\mathbb{Q}^{6}$ | $\mathbb{Q}^{7}$ | $\mathbb{Q}^{n}$ | |
---|---|---|---|---|---|---|---|

Upper bound | 2[15] | 2[4] | 4[1] | ||||

Lower bound | 2[15] | 2[4] | 4[1] | 7[6] | 10[7] | 13[7] | $(1.173+o(1))^{n}$[10] |

For more information on the lower bounds for the chromatic numbers of $\mathbb{R}^{n}$ see [13].

# References

- 1 M. Benda and M. Perles. Colorings of metric spaces. Geombinatorics, 9(3):113–126, 2000. Zbl 0951.05037.
- 2 David Coulson. A $15$-colouring of $3$-space omitting distance one. Discrete Math., 256:83–90, 2002. Zbl 1007.05052.
- 3 K. J. Falconer. The realization of distances in measurable subsets covering $\mathbb{R}^{n}$. J. Combin. Theory Ser. A, 31:184–189, 1981. Zbl 0469.05021.
- 4 Peter D. Johnson. Coloring abelian groups. Discrete Math., 40:219–223, 1982. Zbl 0485.05009.
- 5 D. G. Larman and C. A. Rogers. The realization of distances within sets in Euclidean space. Mathematika, 19:1–24, 1972. Zbl 0246.05020.
- 6 Matthias Mann. A new bound for the chromatic number of the rational five-space. Geombinatorics, 11(2):49–53, 2001. Zbl 0995.05051.
- 7 Matthias Mann. Hunting unit-distance graphs in rational $n$-spaces. Geombinatorics, 13(2):86–97, 2003.
- 8 Radoš Radoičić and Géza Tóth. Note on the chromatic number of the space. In Discrete and computational geometry, volume 25 of Algorithms Combin., pages 695–698. Springer, Berlin, 2003. Zbl 1071.05527.
- 9 Andrei M. Raigorodskii. On the chromatic number of a space. Russian Math. Surveys, 55(2):351–352, 2000. Zbl 0966.05029.
- 10 Andrei M. Raigorodskii. Borsuk’s problem and the chromatic numbers of some metric spaces. Russian Math. Surveys, 56(1):103–139, 2001. Zbl 1008.54018.
- 11 Andrei M. Raigorodskii. Available at http://www.mccme.ru/mmmf-lectures/books/index.php?task=video, 2002.
- 12 D. E. Raiskii. The realization of all distances in a decomposition of the space $\mathbb{R}^{n}$ into $n+1$ parts. Math. Notes, 7:194–196, 1970. Zbl 0202.21702.
- 13 László A. Székely. Erdős on unit distances and Szemerédi-Trotter theorems. Preprint is at http://www.math.sc.edu/ szekely/, 2002.
- 14 Carsten Thomassen. On the Nelson unit distance coloring problem. Amer. Math. Monthly, 106(9):850–853, 1999. Zbl 0986.05041. Available online at JSTOR.
- 15 D. R. Woodall. Distances realized by sets covering the plane. J. Combin. Theory Ser. A, 14:187–200, 1973. Zbl 0251.50003.
- 16 K. Cantwell. Finite Euclidean Ramsey theory. J. Combin. Theory Ser. A, 73:273–285, 1996. Zbl 0842.05064.
- 17 O. Neuchushtan. On the space chromatic number. Discrete Mathematics. 256:499–507, 2002. Zbl 1009.05058.

## Mathematics Subject Classification

05C15*no label found*52C10

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections