Distance graph on <f>Zn</f> with <f>ℓ1</f> norm

A long-standing open problem in combinatorial geometry is the chromatic number of the unit-distance graph in <f>Rn</f>; here points are adjacent if their distance in the <f>ℓ2</f> norm is 1. For <f>n=2</f>, we know the answer is between 4 and 7. Little is known about other dimensions. The subgraphs induced by the rational points have been studied with limited success in small dimensions.We consider the analogous problem on the <f>n</f>-dimensional integer grid with fixed distance in the <f>ℓ1</f> norm. That is, we make two integer grid points adjacent if the sum of the absolute differences in their coordinate values is <f>r</f>. Let the chromatic number of this graph be <f>χ(Z,r)</f>.The main results of this paper are (i) <f>χ(Zn,2)=2n</f> for all <f>n</f>, and (ii) <f>(1.139)n⩽χ(Zn,r)⩽(1/√ of 2πn)(5e)n</f> for all <f>n</f> and even <f>r</f>. We also give bounds useful for small values of <f>n</f> and <f>r</f>. We also consider the lower and upper bounds on the <f>n</f>-dimensional real space with unit distance under <f>ℓp</f> norm for <f>1⩽p⩽∞</f>. [Copyright &y& Elsevier]