A364002 The chromatic number of the Euclidean distance graph G(Z^3, sqrt(n)).

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

Table of n, a(n) for n=1..50.

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

Adjacent sequences: A363999 A364000 A364001 * A364003 A364004 A364005

Keyword

nonn,more

Author

Matt Noble, Jun 30 2023

Status

approved