login
A364002
The chromatic number of the Euclidean distance graph G(Z^3, sqrt(n)).
0
2, 4, 2, 2, 2, 3, 1, 4, 2, 3, 2, 2, 2, 4, 1, 2, 2, 4, 2, 2, 2, 3, 1, 3, 2, 4, 2, 1, 2, 3, 1, 4, 2, 3, 2, 2, 2, 4, 1, 3, 2, 3, 2, 2, 2, 3, 1, 2, 2, 4
OFFSET
1,1
COMMENTS
Let d be equal to the square root of a positive integer n. The graph G(Z^3, d) has its set of vertices being the 3-dimensional integer lattice Z^3. Two vertices are adjacent if and only if they are a Euclidean distance d apart. The chromatic number of G(Z^3, d) is equal to the minimum number of colors needed to color Z^3 so that no two points distance d apart receive the same color. Note that this chromatic number is 1 when d is not realized as a distance between points of Z^3.
The known values of this sequence come from results (or corollaries of results) in the papers linked below. At present, it appears that this chromatic number is only unknown when each of the following holds for the integer n: (1) the squarefree part of n is even, (2) the squarefree part of n has at least one odd prime factor congruent to 2 modulo 3, (3) n is congruent to 2 modulo 3.
LINKS
M. Benda and M. Perles, Colorings of metric spaces, Geombinatorics 9 (3), 113-126.
T. Chow, Distances forbidden by two-colorings of Q^3 and A_n, Discrete Math. 115 (1993), 95-102.
P. D. Johnson, Jr., Two-colorings of a dense subgroup of Q^n that forbid many distances, Discrete Math. 79 (1990), 191-195.
V. O. Manturov, On the chromatic number of integer and rational lattices, J. Math. Sci. 214 (5) (2016), 687-698.
M. Noble, On 4-chromatic subgraphs of G(Q^3, d), Australa. J. Combin. 65 (1) (2016), 59-70.
CROSSREFS
Sequence in context: A284690 A064132 A072865 * A322728 A179686 A286479
KEYWORD
nonn,more
AUTHOR
Matt Noble, Jun 30 2023
STATUS
approved