# Can I finitely color Z^2 such that (x,a) and (a,y) are different for every x,y,a?

I ran into this obstacle in a harmonic analysis problem; I know epsilon about coloring problems.

Is it possible to finitely color Z^2 so that the points (x,a) and (a,y) are differently colored for every x, y and a in the integers (excepting, of course, the trivial cases x=y=a)?

• I don't know if there's a better place to put this, but here's a follow-up question: what do the smallest subgraphs that require k colors look like? Before I worked out the solution below, I had trouble finding anything that that wasn't three-colorable. As per my proof, <sup>2</sup> minus the diagonal should require four colors, but 110 vertices seems like overkill. Is there a smaller example for k=4? – Jonah Ostroff Oct 24 '09 at 15:40
• Oops, that should be ^2, so 90 vertices. Still seems too big, though. – Jonah Ostroff Oct 24 '09 at 16:10
• Oh, here we go. 7 vertices: {(1,1), (1,2), (2,1), (1,3), (3,1), (2,3), (3,2)}. This is the four-chromatic graph generally used to show that the unit-distance plane graph isn't three-colorable (in the sense of the Hadwiger-Nelson problem), plus a few edges. I suspect it's minimal, though I could be wrong. – Jonah Ostroff Oct 24 '09 at 16:40
• And now with 6, for anyone still interested: {(1,1), (1,2), (2,1), (2,2), (2,3), (3,1)} – Jonah Ostroff Oct 29 '09 at 22:39