Article ID Journal Published Year Pages File Type
429705 Journal of Computer and System Sciences 2008 30 Pages PDF
Abstract

The chromatic number of the plane is the smallest number of colors needed in order to paint each point of the plane so that no two points (exactly) unit distance apart are the same color. It is known that seven colors suffice and (at least) four colors are necessary. In order to understand two and three colorings better, it is interesting to see how large a region can be and still be two or three colorable, and how complicated the colorings need to be. This paper gives tight bounds for two and three coloring regions bounded by circles, rectangles, and regular polygons. In particular, a square is 2-colorable if and only the length of a side is , and is 3-colorable if and only the length of a side is .

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics