Vol. 2, No. 3, 2009

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

Volume 17
Issue 3, 363–541
Issue 2, 183–362
Issue 1, 1–182

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

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
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
Editors' interests
ISSN (electronic): 1944-4184
ISSN (print): 1944-4176
Author index
To appear
Other MSP journals
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

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.

four color theorem, Kempe, Kittell
Mathematical Subject Classification 2000
Primary: 05C15, 68R10, 90C35
Received: 23 November 2008
Accepted: 23 November 2008
Published: 3 October 2009

Communicated by Ken Ono
Ellen Gethner
University of Colorado Denver
Department of Mathematics and Department of Computer Science
Denver, CO 80217
United States
Bopanna Kallichanda
4900 S. Monaco Street Suite 200
Denver, CO 80237
United States
Alexander S. Mentis
United States Military Academy
Department of Electrical Engineering and Computer Science
PO Box 67
Fort Montgomery, NY 10922
United States
Sarah Braudrick
Lockheed Martin
12999 W Deer Creek Canyon Rd
Littleton, CO 80127-5146
United States
Sumeet Chawla
6885 West 91st Court, Apt #23-301
Westminster, CO 80021
United States
Andrew Clune
16610 North Black Canyon Highway Suite 100
Phoenix, AZ 85053
United States
Rachel Drummond
OPX Biotechnologies, Inc.
2425 55th Street Suite 100
Boulder, CO 80301
United States
Panagiota Evans
Interactive Intelligence
7601 Interactive Way
Indianapolis, IN 46278
United States
William Roche
1625 S Iola Street #202
Aurora, CO 80012
United States
Nao Takano
Aurora Loan Services
10350 Park Meadows Drive
Littleton, CO 80124
United States