<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-240

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

Artur Czumaj and A.M. Gibbons, Problems on Pairs of Trees and the Four Colour Problem of Planar Graphs (February 1, 1993).

Abstract

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 paper provides 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.

<%@ include file="cited.html" %>

A. Czumaj and A.M. Gibbons, "Problems on Pairs of Trees and the Four Colour Problem of Planar Graphs", 20th International Colloquium on Automata, Languages and Programming (ICALP93), Lecture Notes in Computer Science 700, Springer-Verlag, pp. 88-101 (1993)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>