GUTHRIES PROBLEM - NEW EQUIVALENCES AND RAPID REDUCTIONS

In 1977, Appel and Haken proved that every planar graph is four vertex colourable which finally proved Guthrie's conjecture of circa 1852 th at four colours are always sufficient. Their proof is very long and th e implicit algorithm for four colouring is rather impractical. This pa per provides a new characterisation of the four-colour problem by show ing that it is equivalent (by an optimally fast reduction) to a simply stated problem of 3-edge colouring pairs of toes. This new problem, i n rum, is equivalent to nontrivial subclasses of other problems in mat hematics and computer science of which we describe three. These are pr oblems of intersection of regular languages, of integer linear equatio ns and of algebraic expressions. In the general case, all these proble ms require exponential time to solve. We show that if these problems a re defined on pairs of trees, then polynomial time is sufficient. In a ddition, these problems offer enticing opportunities in the search for a shorter proof of the four-colour theorem and for more practical alg orithms for four-colouring planar graphs.