|
|||||
 |
|
|
|
|
|
How false is
Kempe's proof of the Four Color Theorem? Part II
Ellen Gethner, Bopanna Kallichanda, Alexander S. Mentis, Sarah Braudrick, Sumeet Chawla, Andrew Clune, Rachel Drummond, Panagiota Evans, William Roche and Nao Takano
Vol. 2 (2009), No. 3, 249–265
|
Abstract |
|
We continue the investigation of A. B. Kempe’s flawed proof of the Four Color Theorem from a computational and historical point of view. Kempe’s “proof” gives rise to an algorithmic method of coloring plane graphs that sometimes yields a proper vertex coloring requiring four or fewer colors. We investigate a recursive version of Kempe’s method and a modified version based on the work of I. Kittell. Then we empirically analyze the performance of the implementations on a variety of historically motivated benchmark graphs and explore the usefulness of simple randomization in four-coloring small plane graphs. We end with a list of open questions and future work. |
Keywords
four color theorem, Kempe, Kittell
|
Mathematical Subject Classification 2000
Primary: 05C15, 68R10, 90C35
|
Milestones
Received: 23 November 2008
Accepted: 23 November 2008
Published: 3 October 2009
Communicated by Ken Ono
|
Authors |
| Ellen Gethner | |
| University of Colorado Denver Department of Mathematics and Department of Computer Science Denver, CO 80217 United States |
|
| http://carbon.cudenver.edu/~egethner/ | |
| Bopanna Kallichanda | |
| eCollege 4900 S. Monaco Street Suite 200 Denver, CO 80237 United States |
|
| http://www.linkedin.com/pub/bopanna-kallichanda/4/145/b3a | |
| Alexander S. Mentis | |
| United States Military Academy Department of Electrical Engineering and Computer Science PO Box 67 Fort Montgomery, NY 10922 United States |
|
| http://www.eecs.usma.edu/webs/people/Mentis/ | |
| Sarah Braudrick | |
| Lockheed Martin 12999 W Deer Creek Canyon Rd Littleton, CO 80127-5146 United States |
|
| http://www.linkedin.com/pub/sarah-braudrick/7/22/793 | |
| Sumeet Chawla | |
| 6885 West 91st Court, Apt
#23-301 Westminster, CO 80021 United States |
|
| http://ouray.cudenver.edu/~schawla/ | |
| Andrew Clune | |
| Syntellect 16610 North Black Canyon Highway Suite 100 Phoenix, AZ 85053 United States |
|
| http://www.linkedin.com/pub/andy-clune/4/11/204 | |
| Rachel Drummond | |
| OPX Biotechnologies, Inc. 2425 55th Street Suite 100 Boulder, CO 80301 United States |
|
| http://www.blogger.com/profile/11006794721285468833 | |
| Panagiota Evans | |
| Interactive Intelligence 7601 Interactive Way Indianapolis, IN 46278 United States |
|
| http://www.linkedin.com/pub/panagiota-evans/12/b01/144 | |
| William Roche | |
| 1625 S Iola Street #202 Aurora, CO 80012 United States |
|
| http://www.big-baboon.com/ | |
| Nao Takano | |
| Aurora Loan Services 10350 Park Meadows Drive Littleton, CO 80124 United States |
|
| http://www.linkedin.com/pub/nao-takano/3/964/24 | |
|
