Toward a language theoretic proof of the four color theorem

Bobbe Cooper, Eric Rowland, Doron Zeilberger

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)414-431
Number of pages18
JournalAdvances in Applied Mathematics
Volume48
Issue number2
DOIs
StatePublished - Feb 2012

All Science Journal Classification (ASJC) codes

  • Applied Mathematics

Keywords

  • Four color theorem
  • Parse words

Fingerprint

Dive into the research topics of 'Toward a language theoretic proof of the four color theorem'. Together they form a unique fingerprint.

Cite this