All Unit-Distance Graphs of Order 6197 Are 6-Colorable
✍ Scribed by Dan Pritikin
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 312 KB
- Volume
- 73
- Category
- Article
- ISSN
- 0095-8956
No coin nor oath required. For personal study only.
✦ Synopsis
Consider any 6197 or fewer points in the plane, and create a graph with this vertex set by considering a pair of those points to be adjacent if and only if their distance is exactly 1. It is shown that the vertices of the resulting graph can be properly 6-colored.
1998 Academic Press Consider R 2 =R_R with the Euclidean distance metric d. Let (R 2 , 1) denote the infinite graph with vertex set R 2 where vertices P, Q are adjacent if and only if d(P, Q)=1. A finite graph is called a unit-distance graph if it is isomorphic to a finite induced subgraph of (R 2 , 1). It is known [3] that the chromatic number /(R 2 , 1) equals the maximum chromatic number over all finite unit-distance graphs. It is known that 4 /(R 2 , 1) 7, because the unit-distance Moser graph shown in Fig. 1 is not 3-colorable [5] and because it is not hard to use a regular hexagonal tiling of the plane to construct a proper 7-coloring of (R 2 , 1) [4]. For a survey concerning the unit-distance graph problem, see [1]. The present report consists of progress concerning the upper bound / 7, showing that if a 7-chromatic unit-distance graph exists then it must be quite large, having more than 6197 vertices. FIG. 1. The Moser graph, a 4-chromatic unit-distance graph.