X
PREFACE
History of graph coloring
The origins of graph coloring may be traced back to 1852 when de Morgan
wrote a letter to his friend Hamilton informing him that one of his students had
observed that when coloring the counties on an administrative map of England
only four colors were necessary in order to ensure that adjacent counties were given
different colors. More formally, the problem posed in the letter was as follows:
What is the least possible number of colors needed to fill in any map (real or
invented) on the plane? The problem was first published in the form of a puzzle
for the public by Cayley in 1878. The first "proof" of the Four Color Problem
(FCP) was presented by Kempe in
[198].
For a decade following the publication
of Kempe's paper, the FCP was considered solved. For his accomplishment Kempe
was elected a Fellow of the Royal Society and later the President of the London
Mathematical Society. He even presented refinements of his proof. The case was
not closed, however. Heawood
[158]
stated that he had discovered an error in
Kempe's proof- an error so serious that he was unable to repair it. In his paper,
Heawood gave an example of a map which, although easily 4-colorable, showed
that Kempe's proof technique did not work in general. However, he was able to
use Kempe's technique to prove that every map could be 5-colored. Meanwhile,
progress on the FCP was slow and painful. In 1913 Birkhoff showed that certain
configurations in a map are reducible, in the sense that a 4-coloring of a fragment
of a map can be extended to a coloring of the whole map. This idea of reducibility
turned out to be crucial in the eventual proof of the theorem. In 1976, after many
attempts at solving and partial results on the FCP, Appel and Haken announced
a complete proof, later published in
[7].
This outstanding achievement was based
on the method of "reducible configurations" and a substantial amount of computer
time. The argument of Appel and Haken required a massive computation. It was, in
fact, the first case where the computer assisted researchers in finding the argument
by eliminating a large number of particular cases. This revolutionary incorporation
of computations in the combinatorial proof was met with some skepticism. Later,
Seymour, Robertson et al.
[304]
found a proof of FCT that requires much less
machine involvement. Likely, other researchers will produce a human-checkable
proof soon. Nevertheless it is now clear that combinatorial optimization can use
computers not only as the devices to search, but also as assistants in proofs.
As far as the complexity issue of graph coloring is considered, we have already
mentioned Karp's NP-hardness proof of vertex-coloring
[195].
The next milestone
result is due to Garey and Johnson
[97]
who proved that finding a coloring of
value not worse than twice the chromatic number is NP-hard. Bellare et al.
(18]
strenghtened this result by showing that the problem is not approximable within
n
117
-e:
for any c: 0. The best currently known polynomial-time approximation
algorithm is due to Halld6rsson
[145]
and has O(n(log log n)
2
/
log3
n)
performance
guarantee.
Obviously, coloring a political map is equivalent to coloring the vertices of its
dual planar graph. But a graph also has edges which can be colored. The edge-
coloring problem was posed in 1880 in relation to the FCP. The first paper that dealt
with this subject was written by Tait
[325].
In his paper Tait proved that the FCP
is equivalent to the problem of edge-coloring every planar 3-connected cubic graph
with 3 colors. In 1916 Konig
(214]
proved that every bipartite graph can be d-
edge-colored, where dis the maximum vertex degree. Later, Vizing
(341]
proved a
Previous Page Next Page