Vol. 2, No. 3, 2009

Download this article
Download this article For screen
For printing
Recent Issues

Volume 11, 1 issue

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
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