## HADWIGER'S CONJECTURE

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 proof.) 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 4-cycle subgraphs.) 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 ones. 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.