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