The Library
Guthrie's problem: New equivalences and rapid reductions
Tools
UNSPECIFIED (1996) Guthrie's problem: New equivalences and rapid reductions. In: 20th International Colloquium on Automata, Languages and Programming (ICALP 93), LUND, SWEDEN, JUL, 1993. Published in: THEORETICAL COMPUTER SCIENCE, 154 (1). pp. 3-22. ISSN 0304-3975.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
In 1977, Appel and Haken proved that every planar graph is four vertex colourable which finally proved Guthrie's conjecture of circa 1852 that four colours are always sufficient. 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 an optimally fast reduction) to a simply stated problem of 3-edge colouring pairs of toes. This new problem, in rum, is equivalent to nontrivial 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 solve. 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.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Journal or Publication Title: | THEORETICAL COMPUTER SCIENCE | ||||
Publisher: | ELSEVIER SCIENCE BV | ||||
ISSN: | 0304-3975 | ||||
Official Date: | 22 January 1996 | ||||
Dates: |
|
||||
Volume: | 154 | ||||
Number: | 1 | ||||
Number of Pages: | 20 | ||||
Page Range: | pp. 3-22 | ||||
Publication Status: | Published | ||||
Title of Event: | 20th International Colloquium on Automata, Languages and Programming (ICALP 93) | ||||
Location of Event: | LUND, SWEDEN | ||||
Date(s) of Event: | JUL, 1993 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |