How false is Kempe’s proof of the Four Color Theorem? Part II
How false is Kempe’s proof of the Four Color Theorem? Part II
复制标题
肯普对四色定理第二部分的证明有多错误？
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Nao Takano
中科院分区：
文献类型：
--
作者：
G. Ellen;Bopanna Kallichanda;Alexander S. Mentis;Sarah Braudrick;S. Chawla;Andrew Clune;Rachel Drummond;Panagiota Evans;William Roche;Nao Takano
我们从计算和历史的角度继续调查a . B. Kempe对四色定理的有缺陷的证明。Kempe的“证明”产生了一种平面图着色的算法方法，有时会产生需要四种或更少颜色的适当顶点着色。我们研究了肯普方法的递归版本和基于I. Kittell工作的修改版本。然后，我们实证分析了实现在各种历史动机基准图上的性能，并探讨了简单随机化在四色小平面图中的有用性。最后，我们列出了一系列悬而未决的问题和未来的工作。
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.