Help understanding the chromatic numbers of the planes upper bound.

586 Views Asked by At

I've been studying the Chromtic number of the plane and it shows that a hexagonal tiling of seven colors shows that 7 is an upper bound. 7 color tiling

I couldn't actually follow the argument that proves this is an upper bound.

My problem is why can't the same argument be made by a tiling like 4 coloring or alternate tiling which both only have four colors.

What makes the original tessellation an upper bound but not the four color one's?

1

There are 1 best solutions below

0
On BEST ANSWER

In the first diagram, take the unit of distance to be slightly greater than the diameter of a hexagon. Then it's clear that two points of the same color can't be exactly one unit apart: if they're in the same hexagon, they're too close, and if they're in different hexagons of the same color, then they're too far apart.

Now look at your hexagonal tiling. What are you going to take as the unit distance? It must be greater then the diameter of a hexagon, or else two vertices in the same hexagon will be a unit distance apart. But the distance between two nearby blue hexagons is less than the diameter of a hexagon; so, in order to keep from having two points in nearby blue hexagons a unit distance apart, the unit distance must be greater than the diameter of the union of two nearby blue hexagons; and so forth.