Toward a language theoretic proof of the four color theorem |
| |
Authors: | Bobbe Cooper Eric Rowland Doron Zeilberger |
| |
Institution: | 1. School of Mathematics, 206 Church St. S.E., Minneapolis, MN 55455, USA;2. School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada;3. Department of Mathematics, Rutgers University, Piscataway, NJ 08854, USA |
| |
Abstract: | This paper considers the problem of showing that every pair of binary trees with the same number of leaves parses a common word under a certain simple grammar. We enumerate the common parse words for several infinite families of tree pairs and discuss several ways to reduce the problem of finding a parse word for a pair of trees to that for a smaller pair. The statement that every pair of trees has a common parse word is equivalent to the statement that every planar graph is four-colorable, so the results are a step toward a language theoretic proof of the four color theorem. |
| |
Keywords: | 05A05 05C15 68R15 68Q42 |
本文献已被 ScienceDirect 等数据库收录! |
|