Skip Navigation

Scholars Day 2005, Wednesday, April 13

An Alterative Approach to the Problem of Coloring Planar Graphs

The famous Four-Color Problem of Planar Maps was first posed in 1852 and was only solved in 1977. But the 1977 proof required hours of computer time, and was considered unsatisfactory by many mathematicians. The Four-Color Problem is equivalent to a problem of optimally edge-coloring pairs of same-sized binary trees. We present recent results and open problems concerning the “coloring pairs of binary trees” problem, which could lead to a more elegant proof of the Four-Color Problem. This approach is based on the well-known rotation operation of binary trees.

Presenter: Joan Lucas (Faculty)
Topic: Computer Science
Location: 104 Edwards
Time: 4:05 pm (Session V)