The Chromatic Number of the Euclidean Plane
Except where reference is made to the work of others, the work described in this thesis is
my own or was done in collaboration with my advisory committee. This thesis does not
include proprietary or classi ed information.
Anna E. Boro nska
Certi cate of Approval:
Michel Smith
Professor
Mathematics and Statistics
Krystyna Kuperberg, Chair
Professor
Mathematics and Statistics
Andras Bezdek
Professor
Mathematics and Statistics
George T. Flowers
Dean
Graduate School
The Chromatic Number of the Euclidean Plane
Anna E. Boro nska
A Thesis
Submitted to
the Graduate Faculty of
Auburn University
in Partial Ful llment of the
Requirements for the
Degree of
Master of Science
Auburn, Alabama
August 10, 2009
The Chromatic Number of the Euclidean Plane
Anna E. Boro nska
Permission is granted to Auburn University to make copies of this thesis at its
discretion, upon the request of individuals or institutions and at
their expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
Vita
Anna El_zbieta Boro nska was born on March 2, 1975, in Mys lowice, Poland. She grad-
uated from the mathematics and physics program of Maria Konopnicka General Lyceum in
Katowice, in 1994. She then attended the Catholic University of Lublin for  ve years and
graduated with a Master Degree of Arts in Law in May of 1999. Thereafter, she worked
in Department of Legal Supervision, Silesian Voivodship O ce in Katowice. From 1999 to
2003, she completed curriculum of the doctoral program in Law at the Catholic University
of Lublin. She underwent legal training in the O ce of the District Attorney in Katowice
from 2001 to 2004. Subsequently, she passed Prosecutor?s Examination at Court of Appeal
in Katowice. She obtained a license of a legal adviser in Poland in 2005. She entered the
Graduate Program at Auburn Univerity in August of 2007, as a collaborative student in
the PhD program in Public Administration and Public Policy, and the MS program in
Mathematics. She is married and has a son.
iv
Thesis Abstract
The Chromatic Number of the Euclidean Plane
Anna E. Boro nska
Master of Science, August 10, 2009
(M.A., Catholic University of Lublin, 1999)
30 Typed Pages
Directed by Krystyna Kuperberg
We discuss the chromatic number of the plane problem. We provide a detailed history
of its origins, along with some of the recent progress. Then we describe a proof, based on
[1], of the following result.
Theorem 0.1 Every distance excluding coloring of a locally  nite plane tiling, with the
property that the whole interior of any tile is colored by a single color, must employ at least
six colors.
The result was originally proved for polygonal tilings that have convex tiles, and the area
of all tiles from the tiling bounded from below by a constant. It follows from our proof
that the second condition is redundant. Moreover, using the fact that any polygon can be
triangulated, Coulson?s result is extended to tilings with non convex polygons.
v
Acknowledgments
The author wishes to thank the Committee Members for support and encouragement
during the author?s time of study in the Department of Mathematics and Statistics at
Auburn University. The author is especially indebted to her advisor Dr. Krystyna Kuper-
berg.
vi
Style manual or journal used Journal of Approximation Theory (together with the style
known as \aums"). Bibliograpy follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (speci cally LATEX)
together with the departmental style- le aums.sty.
vii
Table of Contents
List of Figures ix
1 History of the problem 1
2 Preliminaries 9
3 Chromatic number of plane triangulations 11
Bibliography 21
viii
List of Figures
1.1 The Moser Spindle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 The example of Hadwiger . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 The hexagonal 7 coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 The example of Szekely . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.1 Five colors are needed. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Proof of lemma 3.4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3 The regular hexagon H around the tri-colored vertex T. . . . . . . . . . . . 16
3.4 Proof of lemma 3.6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.5 Proof of lemma 3.7. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.6 Six colors are needed. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
ix
Chapter 1
History of the problem
The chromatic number of the plane problem asks for the minimum number of colors
that are needed to paint all points in the plane, so that no two points in a given distance are
colored alike. The question seems very natural and basic, but is yet to be fully answered.
The problem goes back to 1950, when Edward Nelson, a graduate student at the University
of Chicago at the time, created the problem working on the well known four-color problem.
He passed the problem to other mathematicians at the University of Chicago, and soon the
question about the chromatic number of the plane became well known in the mathematical
community (see[6]). The problem sometimes is incorrectly credited to other mathematicians
such as Paul Erd os, Martin Gardner, Hugo Hadwiger, or Leo Moser. Actually, the question
was probably published for the  rst time in Martin?s Gardner \Mathematical Games" col-
umn in \Scienti c American" in 1960 [3]. Although in last nearly 60 years the chromatic
number of the plane resisted all e orts aiming at an ultimate answer, a considerable amount
of research discussing partial answers to this problem, or investigating related problems, ac-
cumulated in the mathematical literature. The following bounds on the chromatic number
are well known:
4 chromatic number of the plane  7.
We shall explain how these bounds are obtained. At this point, however, let us mention that
it has been recently shown by Saharon Shelah and Alexander Soifer [7], [8] that the answer
to the problem may depend on the choice of axioms of set theory. Although in the present
thesis we will consider only geometric aspects of the problem and will not explore those
which belong to set theory, in this section for completeness sake, we shall brie y describe
the results obtained by these authors.
1
Nelson was the  rst to o er a proof of the lower bound. It was published in [4], however
credit was given to his peer John Isbell (see [6]). An independent proof for the lower bound
comes from Leo Moser and William Moser, commonly known as the Moser Spindle [5]. We
will describe the two examples from [4] and [5], starting with the Moser Spindle.
a
b
c
d
e
f
g
Figure 1.1: The Moser Spindle
Consider a graph exhibited in Figure 1.1. All edges are of unit length. Suppose this
graph can be painted by three colors only, excluding unit distance. First consider the
equilateral triangle abc. To exclude the distance 1, all three of these vertices must be of
three di erent colors. Since the equilateral triangle acg shares the edge [a;c], vertex g must
be of the same color as b. On the other hand, in the triangle bed we must use the same two
colors as for [a;c] in order to color the edge [e;d]. Again, the triangle fed shares an edge
[e;d] with bed, and therefore f must be colored alike to b. Clearly, g and f are colored alike
and are unit distance apart. This results in a contradiction.
An alternative proof of the lower bound is provided by the example in [4]. Suppose
only three colors are used to color the entire plane, with the unit distance excluded. Let a
be a point in the plane. Consider a unit circle C around a. No point on C can be colored
2
by the same color as a. Now consider also S, a circle centered at a and of radius p3. Let
a w
z x
?3
1
1
1
C
S
Cx
Figure 1.2: The example of Hadwiger
x be any point on S, and let Cx be a unit circle centered at x. Clearly Cx intersects C in
two points, say w and z. Now notice that w;z;x;a are vertices of a unit rhombus. Since
one of its diagonals is of length p3, the other one must be of unit length. This means that
w and z are unit distance apart and therefore they must be colored by two di erent colors,
both distinct from the one used to paint a. Consequently, since x is a unit distance apart
from w and z, x must be painted alike to a. However, x was chosen arbitrarily on S, and
therefore the entire S must be painted by the same color as a. This is a contradiction, since
on S there are points a unit distance apart, and they can?t be colored alike .
Isbell [4] is credited as  rst to estimate the upper bound using hexagonal coloring of
the plane, with seven colors (see [6]). An alternative proof comes from L. Szekely employing
tiling by squares [10]. We exhibit Isbell?s idea in the following  gure. The description is
3
1
2
3
4
5
6
7
1
2
3
4
5
6
7
1
2
3
4
5
6
7
1
2
3
4
5
6
7
Figure 1.3: The hexagonal 7 coloring
based on [4]. The idea is to color a hexagonal tilling by seven di erent colors. The hexagons
from the tiling are regular and of side length 25. We choose a hexagon and color it by the
 rst color. Then there are six hexagons each sharing an edge with this initial one. We assign
one of the remaining six colors to each of them. Extend the coloring to the hexagonal tiling
of the plane as shown in Figure 1.3. The boundary points on a given edge are colored
arbitrarily by any of the two adjecent colors.
This coloring is unit distance excluding. To see this,  rst focus on interior points of
the hexagons. If we start with hexagons with a side length 25 then no two points of the
same color can be d distance apart, for any d between 45 and
p28
5 . Clearly, no two points
from the same hexagon are in a distance grater than 45 apart (this is the length of the great
diameter). To obtain the other number, consider the isosceles triangle given by dotted lines
in the  gure. Clearly, the side length of this triangle gives the minimal distance between
4
two points colored alike, but from two di erent hexagons (in the  gure the triangle refers
to blue color, or 5). The base of this triangle is the smaller diameter of the hexagon, and
therefore its length equals 2
p3
5 . On the other hand, it is not hard to check that the height of
this triangle is equal to the length of the great diameter, plus side length, minus the height
of the isosceles triangle with sides of length 25 and base 2
p3
5 . Therefore the height of this
dotted triangle is 45 + 25  15 = 1. Consequently the side length is
q
12 + (
p3
5 )2 =
p28
5 . As
far as boundary points are concerned, by the inequality on d, there is enough cushion so
that it doesn?t matter which of the two adjacent colors is assigned to each edge (see [9]).
Szekely?s example is obtained by considering in nite rows of squares in the plane. Each
square is of side length 1p2. We start with an arbitrary square and color it with the  rst
color. Moving in the row from left to right we color squares with subsequent six colors, and
then we start over again with the  rst one. We use a reversed order of colors when moving
to the left in this row. Now,  ll in the plane by identical copies of this initial row. Moving
0 1 2 3 4 5 6 0 1 2 3 4
2 3 4 5 6 0 1 3 42 3 4
4 5 6 0 1 2 3 4 5 6 0 1
0 1 2 3 4 5 6 0 1 2 36
0 1 2 3 4 5 6 0 1 25 6
Figure 1.4: The example of Szekely
downward, let every subsequent row be shifted by 1p2 + 1:1 units to the left. When moving
upward shift by the same factor but to the right. Upper and right boundaries are included
in the color of each square, except for the square?s upper left and lower right corners (see
[9]). It should be clear from the picture that this coloring of the squares, with seven di erent
colors, is unit distance excluding. This is because the closest that two points colored alike,
5
but from two di erent squares, can be is 1:1. On the other hand the diagonal of each of the
squares is of length 1.
Now, let us move on to the results presented by Shelah and Soifer. The authors consider
an equivalent formulation of the chromatic number of the plane problem. Namely, let U2
be a graph on the set of all points of the plane as its vertex set, with two points adjacent i 
they are 1 distance apart. The question now is: What is the minimal number of colors that
need to be employed in order to color every vertex of this graph, with no two points adjacent
colored alike? Finite subgraphs of of U2 are called  nite unit distance plane graphs. In 1951
it was shown by Erd os and Nicolaas de Bruijn [2] that the chromatic number of the plane
is attained on some  nite subgraphs. This fundamental result determined much of research
to go in the direction of  nite unit distance graphs, but at the same time, implicitly, was
dependent on the axiom of choice. Motivated by this result, Shelah and Soifer consider how
the above question may depend on the following axioms of set theory.
(AC)(Axiom of choice) Every family  of nonempty sets has a choice function; i.e., there
is a function f such that f(S)2S for every S from  .
(AC@0)(Countable axiom of choice) Every countable family of nonempty sets has a choice
function.
(DC)(Principle of dependent choices) If E is a binary relation on a nonempty set A, and
for every a2A there is b2A with aEb, then there is a sequence a1;a2;::: such that
anEan+1 for every natural number n.
(LM) Every set of real numbers is Lebesgue measurable.
(ZF) Zermelo-Fraenkel system of axioms of set theory.
(ZFC) ZF with an addition of AC.
Axiom DC is a weak form of axiom AC, whereas axiom DC implies axiom AC@0. In their
 rst paper [7] Soifer and Shelah formulate the following theorem.
6
Theorem 1.1 Assume that any  nite unit distance plane graph has chromatic number not
exceeding 4. Then:
(i) In ZFC the chromatic number of the plane is 4.
(ii) In ZF+DC+LM the chromatic number of the plane is 5,6, or 7.
In the second paper [8] the authors extend the ideas from the  rst paper, giving two inter-
esting examples that illustrate possible correlation of the above axioms of set theory and
the chromatic number of the plane. Their  rst example is as follows.
Let G2 be a graph with <2 as the vertex set, and the set
[
 2F
f(s;t) : s;t2<;s t  2Q2g
as the set of edges, where Q is the set of rationals, and
F =f(p2;0);(0;p2);(p2;p2);( p2;p2)g:
Then
(i) In ZFC the chromatic number of G2 is equal to 4.
(ii) In ZF+AC@0+LM the chromatic number of G2 is not equal to any positive integer n
nor even to @0.
The second example is a modi cation of the  rst one. Namely, G3 is de ned exactly the
same as G2, with the only exception that now
F =f(p2;0);(0;p2)g:
Then
(i) In ZFC the chromatic number of G3 is equal to 2.
7
(ii) In ZF+AC@0+LM the chromatic number of G3 is not equal to any positive integer n
nor even to @0.
In the present thesis we will focus our attention on yet another partial result toward a  nal
solution of the chromatic number problem. D. Coulson in [1] considered special type of
distance excluding coloring of the plane, associated with certain types of polygonal tilings.
He showed that such a coloring must employ at least six colors. In chapter 2 this result is
stated in details in theorem 0.1, whereas the discussion of the proof will follow in chapter 3.
This result was stated for colorings of polygonal tilings of the plane. However, the author
assumed that two polygons from such a tiling meet either at a vertex, or along an entire
common edge. Since any polygon can be triangulated without introducing new vertices, we
will consider only colorings of triangulations of the plane; i.e., polygonal tilings where each
tile is a triangle and the intersection of any two tiles is an edge of both tiles, a vertex, or
empty.
8
Chapter 2
Preliminaries
We will use the following notation. <2 denotes the Euclidean plane with the distance
between two points x;y 2<2 given by jjx yjj = p(x1 y1)2 + (x2 y2)2, where x =
(x1;x2) and y = (y1;y2). For a  xed  > 0 and x2<2, by S (x) we will denote the circle
of radius  centered at x. A closed disk is the region D (x) bounded by S (x).
By a tiling of the plane <2 we will understand a collection of polygons P such that
 SP =<2
 if P1;P22P then IntP1\IntP2 =;.
The interior IntP of a triangle P is the set of all points x for which there is a closed disk
G P centered at x. An interior point of a triangulation is a point that is in the interior
of one of the elements ofP. A boundary point is a point that is not an interior point. Note
that a boundary point is either a vertex of a triangle from P or it lies on an edge of such
a triangle. A polygon P is convex if for given x;y2P the straight segment [x;y] joining
x and y lies entirely in P; i.e. [x;y]  P. A tiling P is locally  nite if for every point
x2<2 there is a circle S centered at x that intersects only a  nite number of elements
from P. A locally  nite tiling P is a triangulation if every element of P is a triangle and
the intersection of any two tiles is an edge of both tiles, a vertex, or the empty set.
A coloring of the plane is a surjective function  : <2 !  , where  is the set of
colors. We will denote these colors by greek letters such as  ; ; ; ; . Given a point x in
the plane, and a color  2 , we shall say that x is  -colored if  (x) =  . We will consider
only colorings with the following property:
 if P is an element of the tilling,  2 is a color, x;y2IntP, and x is  -colored, then
y is  -colored as well;
9
i.e. any element of the tiling has its entire interior colored by the same color.
At this point it is important to address the following issue. We will not deal with
the coloring of the boundary points at all. It is important to stress out that this does not
mean that the coloring function is not de ned for these points. Rather it means that the
main result does not depend on how these boundary points are colored. In other words, a
restriction of the coloring to interior points only already forces that the set of colors must
consists of at least six elements.
We say that a coloring  (x) of the plane is distance excluding if there is a distance d
such that jjx yjj = d implies that  (x) 6=  (y); i.e. no two points of the same color can
be d distance apart. From now on let such a distance d be set once and for all.
The main result that we are going to discuss is as follows.
Theorem: If  :<2 ! is a distance excluding coloring of a locally  nite tiling P, then
 consists of at least six colors.
The above result was originally proved in [1] for locally  nite polygonal tilings with convex
tiles, and the area of all tiles from the tiling bounded from below by a constant. However,
this last assumption is not needed to prove the above theorem, when we assume local
 niteness, as we are going to exhibit. Alternatively, one could drop local  niteness of the
triangulation, and assume the lower bound for the area of all triangles instead, and still
prove the theorem. Also, as mentioned earlier, using the fact that any polygon can be
triangulated allows us to deal only with triangulations, instead of polygonal tilings. This
also allows for a generalization of the result by Coulson, since in such a case we do not need
to state that the elements of the tilings are convex. We can start with any polygonal tiling
P, and after triangulating each of its elements we can consider a triangulation P0. Since
such a triangulation is still locally  nite and every triangle is convex, the same arguments
can be applied.
The rest of the present thesis is devoted to proving the above result. We shall present
in detail a number of arguments that were indicated as true in [1], but an actual proof of
these facts, not immediately apparent, was not given.
10
Chapter 3
Chromatic number of plane triangulations
From now on, let  : <2 !  be a distance excluding coloring of a triangulation P
set once and for all, and let d be the excluded distance. We shall say that a vertex T is
tri-colored if T belongs to three triangles from P, each of which has its interior painted by
a color di erent than the interiors of the other two. Similarly, a vertex is bi-colored if it
belongs to two triangles that are not colored alike.
Lemma 3.1 There is a tri-colored vertex T in the triangulation P.
Proof: Suppose to the contrary that there is no tri-colored vertex. Choose a triangle P
and a subcollection G of the triangulation, that is maximal with respect to the following
properties:
1. P 2G,
2. if ~P 2G then IntP and Int ~P are colored alike,
3. SG is connected.
Notice that SG is bounded. Suppose it was not. Choose x2IntP and consider the circle
Sd(x) of radius d centered at x. Since SG is not bounded by Sd(x) there must be a point
y2Sd(x)\SG. If y is an interior point then we obtain a contradiction, since x and y would
be colored alike, and in distance d apart. If y is a boundary point to a triangle ~P from G,
then choose an  and a circle S (x) around x small enough so that S (x)  IntP. Also,
choose  1  so that the circle S 1(y) intersects the interior of ~P. Let z2S 1(y)\Int ~P and
let Sd(z) be the circle centered at z of radius d. Clearly Sd(z) intersects S 1(x) in a point, say
w. Since S 1(x) S (x) therefore w and z are colored alike. This is a contradiction, since
11
jjw zjj= d. We have obtained that SG is bounded. Consider the complement of SG; i.e.
consider <2nSG. There is an unbounded set U, that is a component of this complement.
Notice that the boundary of U separates the plane (no point in the complement of U can
be joined by a line segment with a point in U, without crossing this boundary) therefore
this boundary must contain a closed loop, say L. L is a union of edges, each of which is
shared by a triangle from G and by a triangle from PnG.
Consider a subcollection U of all triangles R from PnG that intersect L. Notice that
all elements fromU are colored alike. Indeed, suppose the contrary. Pick a triangle P1 from
U with an edge contained in L. Suppose, there was a triangle P2 in U, colored not alike
to P1. Choose an edge E1  L of P1, and an edge E2  L of P2. Since L is connected,
there is a path Y consisting of edges that joins E1 with E2 (with possible self-intersections).
By the initial assumption there is no tri-colored vertex in this path, and therefore every
vertex is bi-colored. Let  be the color of G,  be the color of P1, and  the color of P2.
Walking from E1 to E2 along Y, let v1 be the  rst bi-colored vertex where  -colored and
 -colored triangles meet. Backtrack to the previous vertex v2. At this vertex  -colored and
 -colored triangles meet. Consider the edge [v2;v1]. This edge is shared by exactly two
triangles, one of which is a triangle P32G, which in turn must be  -colored. Let P4 be the
triangle fromU sharing [v2;v1] with P3. If P4 is  -colored then v1 is tri-colored. Otherwise
v2 is tri-colored. We obtained a clear contradiction, since we assumed there is no tri-colored
vertex, and therefore all elements of U are colored alike.
Now, complete U so that SU is maximal with respect to two properties:
1. if P1;P22U then IntP1 and IntP2 are colored alike,
2. SU is connected.
Choose an interior point p2SU. If the circle Sd(p) of radius d centered at p intersects SU,
then we obtain a contradiction by the same arguments that were used to exhibit that SG is
bounded. Otherwise, repeat the same reasoning as before replacingG withG[U. The local
 niteness of the tilling assures that the region bounded by SU will be expanding (otherwise,
12
the areas of triangles would need to tend to zero, and there would be an accumulation point,
by Bolzano Weirstrass theorem-cf. proof of proposition 3.2) and, if neccesary, iterating the
above procedure  nitely many times we will obtain a contradiction.
Proposition 3.2 Let C be a circle. Then there are only  nitely many boundary points on
C.
Proof: Notice that by local  niteness of the tilling, C can have a nonempty intersection with
only  nite number of elements from the triangulation. A contrario, suppose C intersects
in nitely many triangles from the triangulation. By Bolzano-Weirstrass theorem, applied
to a circle, there must be an x2C, such that for any given circle S around x there are
points from in nitely many of these triangles in S\C. Therefore the triangulation is not
locally  nite at x. A contradiction.
Now, we will show that any tile can have only  nitely many boundary points on C.
Suppose to the contrary that there is a tile P that has an in nite number of boundary
points on C.
First, in nitely many of these points must be interior points of edges of P, since P has
only  nitely many vertices. Second, for given edge E of P there are at most 2 points in
common for E and C, since any straight arc intersects a circle in at most 2 points. This
implies that if there are in nitely many boundary points of P on C, there must be also
in nitely many edges of P. But P is a triangle. Contradiction.
Consequently, C has nonempty intersection with only  nitely many tiles, each of which
has only  nitely many boundary points on C.
Lemma 3.3 The set of colors  must consists of at least  ve colors.
Proof: Let C be a circle of radius d and centered at the tri-colored vertex T. By
proposition 3.2 there are only  nitely many boundary points on C. Let z be any point on
C which is an interior point of a triangle Q. There is an  > 0 such that z is contained in
Q with some closed disk G (z) of radius  centered at z. Clearly G (z) is colored with the
13
T
z w
q
Gepsilon1(z)
Sepsilon1a(T)
Sepsilon1a(z)
Figure 3.1: Five colors are needed.
same color as z. Let  ; ; be the three colors meeting at T. Suppose z is colored by  
and let [z;T] be the straight segment of length d joining T with z. Arbitrarily close to T
there are  -colored points. Therefore there is     such that there is an  -colored point
q on the circle S  (T) of radius   centered at T. Consider the straight segment [q;T] and
along with the segment [z;T] extend it to a parallelogram [z;T;q;w]. Then w is a point on
the circle S  (z) of radius   centered at z. Since S  (z) G (z), w is  -colored, and in a
distance d from  -colored point q. A contradiction.
By the same arguments it can be shown that z can be neither  -colored nor  -colored.
Now let v be a point on C in a distance d from z. By the same reasoning as above v cannot
be either  -colored, or  -colored, or  -colored. Since it is d distance apart from z, it cannot
be of the same color as z, and therefore a  fth color is needed.
In Lemmas 3.4, 3.5, 3.6, 3.7 we assume that only  ve colors are used.
14
Lemma 3.4 Let C be a circle of radius d and centered at the tri-colored vertex T. If
x;y2C, jjx yjj= d and x is a boundary point of two distinct tiles colored by two di erent
colors, then y cannot be an interior point of any tile.
Proof: Suppose  =f ; ; ; ; gis the set of colors, C is the circle of radius d centered
at T and x;y2C,jjx yjj= d. Again, let  ; ; be the three colors meeting at T. Suppose
T
x
q
y
w
Q
W
R
Figure 3.2: Proof of lemma 3.4.
that x is a boundary point of some two tiles, say W;R, colored by two di erent colors, but
y is an interior point of a tile Q. By the reasoning in the proof of lemma 3.3, on the circle
C there can be no interior point colored by  ; or  . Therefore, IntW and IntR must
be colored by  or  . Without loss of generality, suppose IntW is  -colored and IntR is
 -colored. There is  > 0 such that y is contained in Q with a closed disk G (y) of radius  
centered at y. Since we assume there are only 5 colors used, y must be either  -colored or
 -colored. Suppose y is  -colored. x is in the boundary of W and therefore there is     
such that there is a  -colored point w2IntW on the circle S  (x) of radius   centered at
15
x. Consider the straight segment [x;w] and along with the straight segment [y;x] extend
it to a parallelogram [y;x;w;q]. Then q is a point on the circle S  (y) of radius   centered
at y. Since S  (y)  G (y), q is in the interior of Q and therefore it is  -colored, as y is.
However, q is in a distance d from  -colored point w. This gives a contradiction. The same
arguments apply if x is  -colored, and this concludes the proof.
Lemma 3.5 Let C be a circle of radius d and centered at the tri-colored vertex T. Then
there is a regular hexagon H inscribed into C, each vertex of which is a boundary point of
some two tiles colored by two di erent colors.
Proof: Let x be any point on the circle C of radius d around T, where two tiles whose
T
d
d
d
d
d
d d
x
y
H
C
Figure 3.3: The regular hexagon H around the tri-colored vertex T.
interiors are of two di erent colors meet. By lemma 3.4 if y is on on the circle C in the
distance d apart from x, then y is not an interior point. This process can be repeated in
order to obtain four more di erent points with the same property as x and y, since in a
circle of radius d one can inscribe a regular hexagon of side length d. Therefore these six
points span a regular hexagon H inscribed into C and the proof is complete.
16
Let A be a circular subarc of the circle C. We will write A =<v;w> to indicate the
shorter of the two subarcs of C, with endpoints in v and w. We say that A invades the
interior of P if A\IntP 6=;.
Lemma 3.6 Assume that the boundary of C is colored with two colors only. Let H be the
regular hexagon described in lemma 3.5. Let v;w be two vertices of H sharing an edge [v;w].
Let A =< v;w >. By de nition of H there are two triangles meeting at v one  -colored,
and the other  -colored. Suppose Pv is one of the two with v in its boundary and such that
the arc A invades IntPv. Let Pw be de ned analogously for w. Then  (IntPv) =  (IntPw);
i.e. the interiors of Pv and Pw are of the same color.
Proof: Let v;w;Pv;Pw be as described above. Suppose by contradiction the interiors of Pv
T
H
C v
w
PF
Pv
u
z
y
r
Pw
Figure 3.4: Proof of lemma 3.6.
and Pw are not of the same color; i.e. let IntPv be  -colored and IntPw be  -colored. Let
F be the subarc of C such that F = CnA, and let PF be a  -colored triangle from the
triangulation that is invaded by F and meets Pw in w. The existence of such a triangle is
17
guaranteed by de nition of H; since we assume that Pw is  -colored therefore PF must be
 -colored. F invades the interior of PF and there exists a point u2IntPF \F. The entire
subarc <w;u> of F is  -colored (with a possible exception for w). Let z be a point on A
in the distance d from u. Since arc A invades IntPv there must be points from Pv on the
arc < v;z >. Choose y 2 IntPv\< v;z >. Clearly y is of distance d from a point r on
<w;u>. But this is a contradiction, since both z and y are  -colored.
Lemma 3.7 Let H be the regular hexagon described in lemma 3.5, and v;w its two con-
secutive vertices. Let [v;w] be an edge of H, and Rv be a ray starting at v, that makes a
right angle with [v;w]. Then there is an  > 0 and a disk D (v) around v, such that any
point on Rv\D (v) is neither  -colored nor  -colored ( ; are colors meeting at at v).
Proof: Let [u;v] be the edge of H meeting [v;w] at v. By the reasoning of lemma 3.6
T
H
C
v
w
y
u z t
r
Figure 3.5: Proof of lemma 3.7.
without loss of generality we can assume that there is z2[u;w] (close to u) such that (u;z)
18
is colored by a single color. Similarly, we can assume that there is y2 [v;w] (close to w)
such that (y;w) is colored by a single color. Then (u;z) and (y;w) are not colored alike,
and assume that (u;z) is  -colored, but (y;w) is  -colored. Now, there is a point t2Rv
close enough to v so that Sd(t) intersects (y;w). Clearly t cannot be  -colored, nor any
other point on the straight arc [v;t]. Similarly, there is r2Rv close enough to v so that
Sd(r) intersects (u;z). Clearly r cannot be  -colored, nor any other point on the straight
arc [v;r]. The lemma follows with  = minfjr vj;jt vjg.
Theorem: If  :<2 ! is a distance excluding coloring of a locally  nite tiling P, then
 consists of at least six colors.
Proof: Suppose to the contrary, that we can use 5 colors only and exclude the distance
T
B
?
??
?
?
?
?
p1
p2
R1
R2
c
a
b gk
Figure 3.6: Six colors are needed.
d. Consider an edge B with a vertex at T, that belongs to two triangles P1 and P2 such
that T 2P1\P2 and IntP1 is  -colored and IntP2 is  -colored. The ray starting at T and
containing B intersects the hexagon H in a point, say p. Let p1 and p2 be two vertices of
19
the edge of the hexagon H that contains p (possibly p = p1 or p = p2). Notice that both
[p1;T] and [p2;T] make acute angles with B.
Consider the ray R1 starting at p1 that makes a right angle with [p1;p2], and the ray
R2 starting at p2 that makes a right angle with [p1;p2]. Close to p1 and p2, R1 and R2 are
neither  -colored nor  -colored.
Choose a point c on R1 and g on R2 close enough to p1 and p2 respectively, so that the
circles Sd(c),Sd(g) of radius d centered at c and g respectively, both intersect the edge B in
its interior. One can assure that jjc p1jj=jjg p2jj.
Let k be in Sd(c)\B. Observe that there is a circular arc [a;b] Sd(c) containing k
such that the circular segment (a;k) is  -colored and the circular segment (k;b) is  -colored,
by de nition of B. Therefore c cannot be either  -colored or  -colored. Consequently c
must be  -colored. By the same arguments, assuming that only  ve colors are to be used,
g must also be  -colored. However, jjc gjj = d, since both R1 and R2 make right angle
with [p1;p2] (which is of length d) and the straight segment [c;g] is parallel to [p1;p2]. This
contradiction implies that a sixth color, say  is needed, which completes the proof.
20
Bibliography
[1] Coulson, D. On the chromatic number of plane tilings. J. Aust. Math. Soc. 77 (2004),
no. 2, 191-196.
[2] P. Erd os, N.G. de Bruijn, A colour problem for in nite graphs and a problem in the
theory of relations, Indag. Math. 13 (1951) 371-373.
[3] Gardner, M. The celebrated four-color map problem of topology. Sci. Amer. 203 1960
no. 3, 218-226.
[4] Hadwiger, H. Ungel oste Probleme, Nr. 11. Elem. Math. 16 1961 103-104.
[5] Moser, L., Moser, W., Solution to Problem 10, Can. Math. Bull., 4,(1961), 187-189.
[6] Soifer, Alexander Chromatic number of the plane & its relatives. I. The problem & its
history. Geombinatorics 12 (2003), no. 3, 131-148.
[7] Soifer, A. Shelah, S. Axiom of choice and chromatic number of the plane. J. Combin.
Theory Ser. A 103 (2003), no. 2, 387-391.
[8] Soifer, A. Shelah, S. Axiom of choice and chromatic number: examples on the plane.
J. Combin. Theory Ser. A 105 (2004), no. 2, 359{364.
[9] Soifer, Alexander, The mathematical coloring book. Mathematics of coloring and the
colorful life of its creators. Springer, New York, 2009.
[10] Sz ekely, L. A. Remarks on the chromatic number of geometric graphs. Graphs and
other combinatorial topics (Prague, 1982), 312-315, Teubner-Texte Math., 59, Teubner,
Leipzig, 1983.
21