THE FOUR COLOR THEOREM AND THREE PROOFS
I. Cahit[*]
Abstract
In August 2004 the author
has introduced spiral chains for the
maximal planar graphs in the sequel of a non-computer proof of the famous four
color theorem. A year later he
has also given an independent proof
of the equivalent problem of three-edge coloring of bridgeless cubic planar
graphs which is known as Tait’s reduction, also by the use of spiral-chains. Recently I have
considered the well-known Kempe’s fallacious proof from the point of
counter-examples. In case of an
counter-example or bad-example to Kempe’s argument, we have abled to extend the given incomplete
four coloring of the bad-example to an proper four coloring of the whole
maximal planar graph. Here the proof proposed uses double spiral chains which
is started from the undecided node of the graph and traverses clock or
counter-clockwise direction the other nodes in the shape of
two parallel spirals (double-spirals).
INTRODUCTION
The famous four color problem is to color
the regions of a given map using least number of colors so that adjacent
regions have different colors. The story of the problem as well as its known
proofs is very long and tedious [1],[6],[2]. There are several historical false
elegant proofs [7],[9],[10-12]. Many books and articles have been published on
the problem so I leave it to the reader to choose his own selection. Robin Thomas has listed
many equivalent formulations of the four color theorem in [18]. My selection
about the four color problem and theorem
would be shortest and simplest, if there are any.
In recent talk Neil Robertson has said:
“The four-color theorem for planar graphs continues to stimulate the
development of chromatic graph theory. Most mathematicians would like to see
the reliance on the computer in the proof reduced. A direct approach would
involve developments in the theory of Kempe chains [4],[5]. Indirectly, the
dual forms of the theorem involving vertex colorations or facial colorations
generalize in different ways. These extensions should lead to new techniques,
as they are longstanding open problems, and some of these may apply to the
theorem itself”. Good news
about the strong supporters of the computer-aided proofs is the announcement
of Gonthier’s verification of
the correctness of the four-color theorem in Coq [2]. Our aim from this paper
is several fold first is to
convinced the reader that the use of spiral chains would add more visual
abstraction to the proof of the theorem, secondly is the possibility of the use
of spirals in the other similar graph coloring problem and lastly is to show
that the spiral-chain technique is powerful enough to devise a non-computer
proofs for the four color map theorem in three different ways
[8],[15],[16].
In this paper we have summarized the three
proof techniques to four color theorem. Actually except the first one the last
two methods are not really new but the tool “spiral-chain” in
graphs or maps is a new and original idea.
The first idea is to give an algorithmic
direct proof with the termination condition and valid for any given maximal
planar graph, that is we have shown that spiral-chain coloring algorithm always
color the nodes of the maximal planar graph with four colors or less.
The second idea is due to Tait’s
reductions. Long ago P. G. Tait showed that instead of coloring the nodes of a
planar graph, equivalently one can color the edges of bridgeless cubic planar
graph with three colors. We have also given an independent proof of this
conjecture, that is without using four color theorem by defining and using
spiral chains in the cubic planar graphs.
Last idea historically is the oldest, most
elegant and most striking one [4],[5]. I call it this “easy to understand
hard accept” type proof. But
it is true and is based on the Kempe’s inductive proof. Historical fallacious
inductive proof of Kempe have been re-considered by many mathematicians whether
it could be repaired. All attempts so far have been either modification of
Kempe color switching argument or trying to show that random second-time
coloring would not produce an impasse. We have given double spiral chain
coloring method when Kempe's argument fails by the trap of the incomplete
four-coloring that there is always a simple re-coloring of the nodes of a
planar graph so that the undecided node colored properly. Hence our method may
be considered as an completion of fallacious Kempe's inductive proof.
SPIRAL CHAIN COLORING: DIRECT PROOF
Spiral chains can be obtained easily by
selecting edges one by one of the maximal planar graph starting from a vertex
in the outer cycle and get into the inner vertices in all clock-wise (or
counterclock-wise) direction. Since the number of outercycle vertices of a
maximal planar graph is three there are exactly six spiral chains.
Spiral segment.
A spiral segment Si of
S is a sequence of vertices 
such that 
, where k≥1 and vk
is the first such node in 
.
Throughout paper we denote the four colors
by C={B, R, Y, G}={Blue, Red,
Yellow, Green}.
We begin with the normal maps shown in Fig.
1(a) and (b) respectively with 9
and 14 regions (including
the outer-region). Here the term normal is being used to indicate that no more
than three regions meeting at one point. One of the property of these maps are
that the corresponding planar graphs are maximal i.e., faces in the planar
graph are all triangle.
Fig. 1 Maps, spirals
and four coloring.
Let us give some intuitive arguments about
the use of spiral-chains in the coloring of graphs. One of the unwanted task in
any graph coloring algorithm is the backtracking. That is if at any stage we
cannot find free proper color in the k colors and we need to use (k+1)th color
in the k-chromatic graph, in other words
the coloring algorithm should restart in worst right from the beginning or from some previous step and try to
overcome this impasse by coloring the nodes in another way. On the other hand
spiral chain in the maximal planar graph can be considered as a road-map in the
coloring algorithm. In general a node in the spiral chain looks like a way to "cut up" a
graph so that each node is
connected to one of four kinds
of vertices: one node forward of it in the spiral, and one
node behind it, and then a set of
nodes to its "right"
which are bisected by the chain, and another set on the "left" which
are bisected on the other side. Consider now any pairwise neighbor three
sub-spiral chains 
,
in G such that
nodes of (right
sub-chain) have already been
colored completely, nodes of 
(middle
sub-chain) colored partially till the vertex x and all vertices of (left sub-chain)
have not yet been colored. In the spiral chain coloring algorithm in deciding
the color C={B, R, Y, G} of the node
x we need only to consider the
color of the node y on with 
and the color of
the nodes adjacent at x on . In another words while coloring the current node x
we only need to consider the nodes
of right-spiral chain and the color of the vertex y.
(a)
(b)
Fig. 2 Spiral-chain coloring of the map
in Fig. 1(a) and the four color of
the graph corresponding simplified map of Martin Gardner’s (1975) April Fool’s joke (see Fig. 1b).
Example
1. Consider the maximal
planar graph shown in Figure 2 (a) which its core is an empty graph. Spiral segment S1 is a path of length two which
necessarily forms a triangle in G and we color its nodes as R, G, B. Hence the
color class of S1 is 
. Next spiral
segment S2 surrounds S1 so we have to switch color class
C1 to 
. Now the color green GÎC becomes a safe color with respect to C1
since 
and color red RÎC becomes a safe color with respect to C2
since RÏC2. Next we will argue how to color spiral
segments. Let v be any node of Si, i≥2 which has not yet been
colored. For i=1 we don’t put any rules on the node coloring of S1 except we say that any 3-coloring will
do the job.
Example
2. Consider the maximal planar graph shown
in Figure 2 (b) which its core is a single node.
One of its spiral chain S can be easily obtained by starting any outer vertex,
say from the node v9 and
selecting nodes in decreasing order. That is V(S)={v9,v8,…,v1}
and here V(S)=V(G) since spiral chain S is also an hamiltonian path. Spiral
segments of S are S1={v1,v2,v3}
since v3 is the first vertex closing the segment into cycle with the
vertex v1, S2={v4,v5,v6,v7,v8}
since v8 is the first vertex closing the segment into cycle with the
vertex v4 and finally S3={v9} is the spiral
segment without an edge. Three-color classes, the use of safe colors have been
shown in the figure.
Fig 1(a) and (b) illustrate spiral chain
coloring algorithm on the maps.
Node
Coloring Rule (NCR)
While three coloring nodes of a spiral-segment, use non-safe colors whenever it is possible.
Note that at
beginning since we start with the 3-coloring of the first spiral segment we do
not know its safe color till we color the nodes of the next spiral segment of
the spiral-chain.
The following Lemma
accounts the main step towards the non-computer proof of the four color theorem
[6].
Lemma
1. If the nodes of a spiral chain
are all colored by the NCR then
(a) we do not need any
re-coloring of the vertices and furthermore
(a) we do not need the fifth
color.
In case of the
maximal planar graph has more than one spiral chains nothing much changed in
the spiral-chain coloring algorithm. Note that since each spiral segment is
3-colorable we are left one free color for the last outer node on the spiral
chain. This will assure the termination condition of the coloring
algorithm.
SPIRAL-CHAIN TAIT’S COLORING: INDIRECT PROOF
Assuming the four color
theorem (4CT) it is easy to show that every cubic (bridgeless) planar graph has
a three-edge-coloring since Tait found an equivalent formulation of the 4CT in
terms of 3-edge-coloring. Here is the proof.
Assume that the regions of a cubic planar
graphs colored properly by red (R), blue (B), green (G) and yellow (Y) colors.
Then if two neighbor regions are colored by RG or GY then color its boarder
(edge in the cubic graph) by G, if two neighbor regions are colored by RG or BY
then color it boarder by R and if two neighbor regions are colored by RY or BG
then color its boarder by B.
Three edge coloring of cubic planar
graphs is an old-conjecture due to
Tait in the squeal of efforts in
settling the four-color conjecture at the end of the 19th century. Here we will
outline an independent proof of this famous conjecture. Again the proof is rely
on the spiral-chain coloring but rather on the coloring of the edges of a cubic
bridgeless planar graphs [13]. In [13] we have first shown that any cubic
planar graph can be decomposed into vertex disjoint spiral chains which in turn
expressed as the union of folded special spiral caterpillar (spiral-combs).
Then based on the spiral-comb(s) decomposition we have provided a simple
three-edge-coloring algorithm for any given cubic planar graph. In the second
part we have shown that the same method can also be applied to a similar but
more general three-edge cubic graph (non-planar) coloring conjecture of Tutte
which has been recently settled by a series lengthy papers using the classical
four color theorem proof technique. That is
Conjecture. Every
2-connected cubic graph with no Petersen minor is 3-edge colorable.
This extends the four color
theorem as Tait showed that the four color theorem is equivalent to the
statement that every planar 2-connected cubic graph is 3-edge colorable. It
also implies that certain non-planar graphs are 3-edge colorable. Let us say
that G is apex if G╲v is planar for some v and G is doublecross if it can be
drawn in the plane with crossings, but with atmost two crossings and with all
the crossings on the boundary of the finite region. Both apex and doublecross
graphs have no Petersen minor so Tutte's conjecture implies:
Conjecture
(RST). (1) Every 2-connected apex cubic graph is
3-edge colorable and (2) every 2-connected doublecross cubic graph is 3-edge
colorable.
Tutte and RST equivalences
has been shown in [6] that "a minimum counter-example" mean a
2-connected cubic graph G with no Petersen minor which is not 3-edge colorable,
with |V(G)| minimum. That is every
minimum counter-example is either apex or doublecross. Eventually Tutte's
conjecture has been settled by a series of papers [6]-[10] by using the
classical proof method of the four color theorem [12],[13],[14].
In this section we will give
an three edge-coloring algorithm which uses spiral chains of the given cubic
bridgeless planar graph. Let
C={R,O,G}. In the figures we use numbers 1,2,3 on the edges instead of
letters to avoid confusion. Let S be denote a spiral-chain of G. As we go
through the vertices of S we construct a path Ps with nodes v₁,v₂,...,vk
and assume that ∣V(P)∣=∣V(G)∣,i.e., k=n. We will investigate cubic
graphs with several spiral-chains later. Edges incident to Ps together
with the edges E(Ps) of the path constitute a comb-caterpillar tree
Cs(Vs,Es), where Vs={v₁,v₂,...,vk}
and Es=E(Ps)∪{E(Ps): {vi,vj}∣ vi,vj∈V(Ps)
and d(vi,vj)≥2}. An edge b of the Cs is
called the backbone-edge if b∈E(Ps)
and is called the hair-edge h if h∉E(Ps) . It is clear that Cs=G
but some of the edges of E(Ps) are counted twice since any hair-edge
of Cs has two ends in the spiral-chain S. Again as we go through the
edges of S we call that hair edge h∈E(Ps) is real if it is
encountered for the first-time and imaginary if it is encountered for the
second-time. In the figures all the real-hair edges have been shown in
straight-lines while the imaginary-hair edges are shown with dashed-lines. The
importance of the real and imaginary hairs will be clearer when deciding the
color of the current edge in the spiral chain. We have classify the colors into
two classes. The color green G is called as the "primary" color while
the colors orange O and red R are called the "secondary" colors. In
the coloring algorithm given below primary color G is used mostly for the
spiral-chain backbone edges and the secondary colors O and R are used mostly for the hair-edges.
Algorithm A. Spiral-chain edge-coloring (for single
spiral-chain)
Let the cubic planar graph G
be drawn in plane without any crossings. As the first step construct in
clockwise direction a spiral-chain S of G starting from a vertex v₁ of its
outer-boundary cycle. Let Cs be the corresponding comb of S. Start
coloring the edges of the backbone edges of Cs alternatingly by
green and orange colors i.e., (G,O)-chain and the hair edges of Cs
by the red R color. If all vertices
of S is covered and edges incident to vertices are properly colored by G,O, and
R then the coloring is the desired proper three edge-coloring.
a) If for some backbone edge
ei=(vi,vi-1) is forced to be colored by R because of the color (it must be orange
O since G is primary color) of the
hair hi-1 at vi-1. Furthermore if the hair hi had
been colored by R before then both ei and hi would be R.
In this case there must be a node vj, with j>i and a spiral
sub-path P(vr,vs), with s>r<j>i. But the path
P(vi,vj)=(vi,vr)∪ P(vr,vs)∪(vs,vj)
is a (R,O)-Kempe chain, where (vi,vr) and (vs,vj)
are the hair-edges. Therefore we perform Kempe-chain color switching for the
edges of P(vi,vj) and resolves the problem at vertex vi.
b) If for some backbone edge
ei=(vi,vi-1) is forced to be colored by O
because of the color of the hair hi-1 at vi-1. Furthermore
if the hair hi had been colored by O before then both ei
and hi would be O. In this case there must be a node vj,
with j>i and a spiral sub-path P(vr,vs), with
s>r<j>i. But the path P(vi,vj)=(vi,vr)∪ P(vr,vs)∪(vs,vj)
is a (O,G)-Kempe chain. Therefore we perform Kempe-chain color switching for
the edges of P(vi,vj) and resolves the problem at node vi.
That is in critical cases we
have always suitable Kempe-chain with both ends are hairs of the spiral
comb-tree. Hence we can perform Kempe-chain color switching within the
spiral-chain of G when we needed to resolve color duplication at node vi.This
argument is also valid at the termination of the algorithm. That is let x be
the last node in the spiral chain S. Then the hairs (z,x)∉S and
(t,x)∉S that have already been colored properly before, from
the point view of the nodes z and
t. Consider the last edge (y,x)∈S. Now if (z,x) and (t,x) have been colored with
orange and red and we can color the current edge (y,x) of S then
spiral-three-edge coloring ends properly. But if (y,x) is forced to be colored
by orange or red because of the coloring condition at the vertex adjacent x in
S then there must be (orange-green)-Kempe chain (respectively
(red-green)-Kempe-chain) start with the orange hair (respectively red
hair-edge) at x and end at some node x. So we perform Kempe-chain switching and
resolve the conflict at the node x. It can be seen that applicability of
Kempe-chain switching rely on the selection of color "green" as the
primary color. That is this time our rule is “use the primary color on
the spiral chain edges whenever possible”.
Fig. 3 and Fig. 4 illustrate the spiral-chain
edge-coloring algorithm.
Algorithm A can be easily
modified to cubic planar graphs having more than one spiral chains. In this
case if the current node, say va of spiral-chain Si
adjacent to two nodes vb,vc
that have already been contained in Si before or in some other
spiral-chain Sj,j<i then we cannot go further. Hence we select
closest new node incident Sk,k=1,2,..,i and start new spiral-chain Si+1
from that node. When all nodes of G covered we obtain node disjoint set of
spiral-chains S₁,S₂,...,Sm. Note that some of spiral-chains
degenerate to a single node. One can easily notice that spiral-chains S₁,S₂,...,Sm
are topologically nested in the plane. Now we are ready to give spiral-chain
edge-coloring algorithm for this case:
Algorithm B. Spiral-chain edge-coloring (for
multiple spiral-chains).
Let S₁,S₂,...,Sm
be the set of spiral-chains of the cubic planar graph. Apply Algorithm A to each spiral-chain Si,i=1,2,...,m.
Note that for each application of Algorithm A we select always the color
"green" G as the primary
color. This selection would minimize execution of number of the steps (a) and (b)
in Algorithm A. That is it will color in green, maximum number of the backbone
edges in the spiral-chains.
Fig.
3. Illustration of the three-edge
spiral chain coloring algorithm.
Fig.
4. Tutte graph and spiral three
edge coloring.
DOUBLE-SPIRAL CHAIN:
KEMPE’S INDUCTIVE PROOF
Most of the mathematicians agree in that bad
(counter-) examples e.g., Heawood [7], de la Vallée-Poussin [11], Errera
[9,10], Kitell [12] -graphs are rare and it is well-known that why Kempe's
method would not work under these examples. Errera example is more elegant than
Heawood's example since requires that all nodes but one be precolored [9, 10].
Therefore we have chosen first a simplified version of Heawood example and then
Errera example in our study. But to the best of my knowledge no one has come up
with an answer of "how we can repair Kempe's proof without going into the
classic proof of the four color theorem"? Although Wagon [13] , Hutchinson
and Wagon [14] have studied possible answer of an similar question, by using
Kittell's random color switching in order resolves the impasse in the Errera
graph.
John Conway once said:
"I
did read a few of the papers from this period, including Kempe's proof, Tait's
deduction of his edge-coloring criterion from it, and an article in which
Heawood pointed out the mistake, among other things, and the impression I got
from them was much the same as Jim's. There was indeed a fair amount of
interest in Kempe's "theorem", but not much evidence that any great
number of people actually scrutinized his proof, or even read it. I don't think
it would have made much difference if they had. The proof is very convincing,
and in the days when the amateur provers were still interested in 4CT (Four
Color Theorem), 2 times out of 3 "Kempe's Catastrophe", as Tom
O'Beirne used to call it, was the proof they'd produce. Tom had a set lecture
in which he gave Kempe's proof, illustrated by a specially made-up board with
colored pegs, and seldom could anyone in the audience find anything wrong with
it."
Next we will consider the
simplified Heawood bad-example. Consider the graph G with 9 nodes shown in Fig.
5 with node coloring, where overlap
circles denote color switching. Initially
the node in the center of cycle of length five, C5, the big-white half-circle below the
big-yellow (e.g., half-white-yellow twin) node is undecided since C5 have been colored with colors Y,B,R,B,G.
Since there are two Kempe-chains; one (G,R)-Kempe chain (red-dashed lines) and
other (Y,R)-Kempe chain so we can switch the colors green and blue nodes on the
left-side and blue and yellow nodes on the right-side node-pairs. Then the
colors of cycle C5 would be {Y,G,R,Y,G} and freeing the color
"blue" to the undecided-node. But then we have c′(va)=c′(vb)=B,
an impasse. This simple example was the source of the long story of the four
color problem.
Before we discuss our solution for this
problem we will give some observations that differs from the others.
·
Since
the six possible Kempe-chains are RG,RG,RY,BG,BY,GY-types, if we increase the
length of one of Kempe-chain, say (RG)-chain, by suitable color switching then
the length of a (BY)-chain would also increases or remain same.
·
Maximum
possible length of a Kempe-chain on C5 is three.
·
In
case of an impasse, instead of switching node colors randomly, assign a new
color (not a fifth color) to suitable existing node- color on C5
so that we can increase the length of Kempe-chain on C5. We call this new color in the incomplete
precolored graph as "joker" color shown as nodes with star in Fig. 5
and 8(a). That is we have changed the number of colors in the color classes.
Let us return to our bad
example. We have chosen the joker color as "blue" and assign it
yellow node of C5 i.e., half-yellow-blue twin node in the Figure 5. Now
we have improper coloring of C5 since its colors are B,B,R,B,G. Then we use
Kempe-switching to the middle three node colors B,R,B (see Fig.5) so that we obtain
new proper three coloring of C5 as
B,R,B,R,G. The impasse is resolved therefore assign yellow color to the
center node. In Fig. 5 we have shown our final four coloring of G which
consisted of two node-disjoint (R,B)-chain (thick blue-line) and (Y,G)-chain
(thick red-line). Note that in the final four coloring of the graph the length
of (R,B)-chain is increased to 4.
We will say more about the shape (double-spiral) of these two disjoint
chains in the next section.
In Fig. 6 we have shown
double-spiral chains decomposition together with its four coloring of the
original "bad-example" designed by Heawood against for the Kempe-argument. It can
easily be checked that the undecided region (with question mark in the figure)
cannot be colored by B,R,G, or Y by using any Kempe chain switching operations.
We note that while (B,G)-Kempe chain in the Heawood's map corresponds to a
single connected acyclic graph (shown in dashed line) the others disjoint, that
is two disjoint (R,Y)-Kempe chains. This is the main reason of the impasse.
However by assigning a de-facto "joker" color instead of existing
region color arround the undecided region, say R, and performing Kempe-chain switching it
is possible to glue the two (R,Y)-chains. Clearly this would resolves the
impasse. In Fig. 5(b) we have shown the final four coloring on the
corresponding maximal planar graph which is again is in the forum of
double-spiral chains.
Excellent survey on the Kempe's method
together with the detailed account of Errera's bad-example has been given by
Hutchinson and Wagon [14]. We have
re-drawn Errera graph, with its incomplete four coloring, by placing the
undecided node u (big white circle)
at the central location of the graph in Fig. 7. That is the node u is clearly
visible as the center of the wheel. We first note that the undecided node u is
surrounded by the cycle C5 and colored with Y,B,G,R,G. Furthermore G,R,G-nodes
of C5 are also
in the (R,G)-chain (close-chain or cycle of length six shown in thick-line in
Figure 7). Now the impasse can be resolved by the following steps:
- Apply Kempe-switching to the (R,B)-close
chain.
- Select the "red" color as the
joker-color and change blue-node in C5 to red. Then color of C5 becomes Y,R,R,G,R. Assign the color blue
to the undecided node u.
- Since the colors of the nodes in C5 is improper we apply Kempe-switching first
to (R,Y)-chain 1 (shown in green-dashed lines in Fig.8) and then to (B,R)-chain
2 (shown in grey-dashed lines in Fig. 8). Now we have Y,R,Y,G,R for the cycle C5 which creates another improper coloring
outside the C5 (red edge
in Fig. 8). We resolve this by enlarging the length of (Y,R)-chain by applying
Kempe-switching to (Y,R)-chain 3. Now the impasse is resolved.
Final four-coloring of
Errera graph is shown in Fig. 8(b) together with its disjoint double-spiral
Kempe chains. It is not difficult to see that for any bad-example to Kempe's
method by using the joker color on
C5 and
enlarging, say (Y,R)-chain by suitable Kempe switching results proper four
coloring of the whole maximal planar graph. It is not difficult to see that for
any given bad-example for the Kempe-method, by selecting suitable
"joker" color and enlarging the Kempe chain result a proper four
coloring in the form of double-spiral chains.
Fig.
5. Simplified Heawood bad-example and double-spiral solution.
Fig.
6. Heawood map and double-spiral coloring.
Fig.
7. Errera’s incomplete four coloring.
Fig.
8. Errera’s incomplete four coloring and its double-spiral solution.
CONCLUSION
Four color problem has been agenda of the
mathematicians not only because of
it’s lengthy computer
aided proofs but also its
puzzle-like character i.e., “show me if you can color it by using only
four colors”. Our main contribution to the solution of this mathematical
enigma is to provide the right tool or the key that is spiral chains in graphs
or maps. It is this tool that enable us to show that the “four color
puzzle” is not different than the solution of the any other solveable
puzzle. We hope that at least in
the future the spiral-chain coloring
solution would replace the positions of the existing
classical solutions. Now the big question remains to be answered, is the next
similar problem with respect to the solution methodology waiting in the line. Is there a
non-computer proof of the Kepler sphere packing conjecture? Who knows may be a
kind of spiral chain traversing the
centers of the face-centered cubic packing of spheres could be used. Time will show us whether this would be
the case or not, but as today we have to be satisfied with the existing proof [3],[17].
References
[1] K. Appel and
[2]
G. Gonthier, “The Four Color Theorem in Coq”, in Types 2004
Conference, December 17, 2004,
[3]
T. Hales, “FLYSPECK: Towards a Formal Proof of the Kepler
Conjecture”, in Types 2004 Conference, December 17, 2004, Thales,
[4] A. B. Kempe, "On
the geographical problem of the four colours", American J. of Math., 2(3),
193-200, 1879.
[5] B. Mohar, "Kempe equivalances of
colorings" preprint, January 2005.
3 : K. Appel and W. Haken, "Every
planar map is four colorable", Contemporary Math., 98, 1989.
[6] N. Robertson, D.P.
Sanders, P.D. Seymour and R. Thomas, "The four colour theorem", J.
Combin. Theory Ser. B., 70 (1997), 2-44.
[7] J. P. Heawood, "On the four-color
map problem", Quart. J. Pure Math., 29 (1898), 270-285.
[8] I. Cahit, "Spiral chains: A new proof
of the four color theorem", preprint arXiv.math.CO/0408247, 18 August
2004.
[9] A. Errera, "Du
colorage des cartes et de quelques questions d'anaysis situs", Thesis,
Gauthier-Villars, Paris, 1921,66pp.
[10] A. Errera, "Exposé
historique de problème des quatre couleurs", Periodico di
Matematische, 7 (1927) 20-40.
[11] de la Vallée-Poussin, Interm.
Math. 3, 179-180, Paris, 1896.
[12] I. Kittell, "A group of operations
on a partially colored map", Bull. Amer. Math. Soc., 41 (1935) 407-413.
[13] S. Wagon, "A
machine resolution of a four-color hoax", CCCG 2002, 174-185.
[14] J. Hutchinson and S.
Wagon, "Kempe revisited", Amer. Math. Monthly 105 (1998) 170-174.
[15] I. Cahit, "Spiral chains:The proofs
of Tait's and Tutte's three-edge-coloring conjectures", preprint
arXiv.math.CO/0507127 v1, 6 July 2005.
[16] I. Cahit, “The
Four Color Map Theorem: Kempe’s Fallacious Proof Repaired”,
preprint, September 2005.
[17] T. C. Hales, “A Proof of the Kepler
Conjecture (DCG Version)”, March 13, 2004, http:// www.math.pitt.edu/~thales/kepler04/fullkepler.pdf
[18] R. Thomas, “An Update on the
Four-Color Theorem”, Notices Amer. Math. Soc., 45(7), 1998, 848-857.
October 4, 2005