On the optimality of coloring with a lattice

For z(1), z(2), z(3) is an element of Z(2), the tristance d(3)( z(1), z(2), z(3)) is a generalization of the L-1- distance on Z(2) to a quality that reflects the relative dispersion of three points rather than two. In this paper we prove that at least 3k(2) colors are required to color the points of Z(2), such that the tristance between any three distinct points, colored with the same color, is at least 4k. We prove that 3k(2) + 3k + 1 colors are required if the tristance is at least 4k + 2. For the first case we show an infinite family of colorings with 3k(2) colors and conjecture that these are the only colorings with 3k(2) colors.