The four-colour problem asks whether every planar graph admits a 4-colouring
(of its vertices, so that any two vertices that are joined by an edge get different
colours). Ever since this was proposed, 150 years ago, it has been one of the
central questions of graph theory; indeed, it was proposed before the subject
of graph theory existed, and much of graph theory grew from attempts to
answer it. It was answered (affirmatively) by Appel and Haken in 1977.
Before it was settled (in 1937) Wagner showed that if it was true, then the following
statement was also true: every graph not contractible to K_5 is 4-colourable.
(In general, K_n means the complete graph with n vertices; and "G is contractible to H"
means that starting from G it is possible to produce H via a sequence of contractions
of edges.) Since planar graphs cannot be contracted to K_5, this statement implies
the four-colour problem, and Wagner showed that in fact it is equivalent.
It is also true (and easy) that all graphs not contractible to K_3 are 2-colourable;
and all graphs not contractible to K_4 are 3-colourable. The natural generalization
was proposed by Hadwiger in 1943:
(Hadwiger's conjecture) For all n, every graph not contractible
to K_n is (n-1)-colourable.
Thus this is easy for n < 4, and very difficult (but equivalent to the four-colour
problem, and therefore true) for n = 4. The next case, n = 5, might be expected
to be even more difficult, but that is not so; the three of us proved that Hadwiger's
conjecture was true for n = 5, in 1993. (We used the four-colour theorem in the
But the remainder of Hadwiger's conjecture, n > 5, remains completely open. We
would like to make an attempt on it.
THE PERFECT GRAPH CONJECTURE
The second problem that we would like to consider is one that the three of us
have much less experience on, but that might yield to the same sort of techniques
that we have used successfully on other problems. Again it concerns graph colouring
and complete graphs, but now there is no contraction of edges. The number of
colours needed to colour a graph (its "chromatic number") is clearly at least
the maximum n such that it has a K_n subgraph (its "clique number"). They are
not necessarily equal; for instance, if G is a cycle of odd length (>3) then
its chromatic number is 3 and clique number is 2. However, for many interesting
classes of graphs, equality does hold, and it would be nice to understand what makes
the difference. But one equation between chromatic and clique number says very little
by itself, so that alone is not the right property to study. There is an inspired
definition due to Berge that captures the right phenomenon nicely. Say a graph G is
"perfect" if the chromatic number of H equals the clique number of H for all
induced subgraphs H of G. (A subgraph H of G is "induced" if it can be obtained
just by deleting vertices and the edges incident with them. Thus for instance
K_4 has no cycle of length 4 as an induced subgraph, though it certainly has
We would like to understand which graphs are perfect. More precisely, is there a
way to construct all such graphs starting from some simple classes by piecing
them together somehow? Is there a way to test quickly whether a graph is perfect?
There is a famous open question here, again due to Berge (1961);
(The perfect graph conjecture): A graph is perfect if and only if neither it not its
complement has an induced subgraph which is an odd cycle of length >3.
(Another way to state the same thing is: the only minimal nonperfect graphs are
odd cycles of length >3 and their complements.)
The area of perfect graph theory has deep and rich connections with linear
and integer programming, and this has been exploited by several people to study the
structure of minimal nonperfect graphs; and now a great deal is known about
these graphs. But it is still not known whether any exist, except for the obvious
Another approach is to try to find a way to construct all graphs G such that neither
G not its complement has an induced subgraph which is an odd cycle of length >3.
Perhaps one could show that they all are composed of pieces that we understand,
put together in some comprehensible way; and then one could try to show that all
such graphs are perfect because of the way they are constructed. This second
approach seems to us to offer a better chance of success, and we would like to
try it, to see if we can get anywhere. We have used similar methods on other
problems, and there ought to be an analogous way to crack this problem.