Problems on pairs of trees and the four colour problem of planar maps

Alan Gibbons

(University of Warwick)

In 1977, Appel and Haken proved that every planar graph is four vertex colourable. Their proof is very long and the implicit algorithm for four colouring is rather impractical. This talk descibes a new characterisation of the four colour problem by showing that it is equivalent, by a very fast reduction, to a simply stated problem of 3-edge colouring pairs of trees. This new problem, in turn, is equivalent to non-trivial subclasses of other problems in mathematics and computer science of which we describe three. These are problems of intersection of regular languages, of integer linear equations and of algebraic expressions. In the general case, all these problems require exponential time to find a solution. We show that if these problems are defined on pairs of trees, then polynomial time is sufficient. In addition, these problems offer enticing opportunities in the search for a shorter proof of the four colour theorem and for more practical algorithms for four colouring planar graphs.
Tuesday 2nd November 1993, 14:30
Seminar Room 322
Department of Computer Science