The Four Color Algorithm
2013, 18(5), pp.113-120
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science
-
This paper proposes an algorithm that proves an NP-complete 4-color theorem by employing a linear time complexity where . The proposed algorithm accurately halves the vertex set of the graph into the Maximum Independent Set (MIS) and the Minimum Vertex Cover Set . It then assigns the first color to and the second to , which, along with , is halved from the connected graph , a reduced set of the remaining vertices. Subsequently, the third color is assigned to , which, along with, is halved from the connected graph , a further reduced set of the remaining vertices. Lastly, denotingas , the algorithm assigns the forth color to . The algorithm has successfully obtained the chromatic number with 100% probability, when applied to two actual map and two planar graphs. The proposed "four color algorithm", therefore, could be employed as a general algorithm to determine four-color for planar graphs.
-
[book] Wikipedia / 2013 / Graph Coloring / Wikimedia Foundation Inc
[book] Wikipedia / 2008 / Four Color Theorem / Wikimedia Foundation Inc
[book] R. Thomas / The Four Color Theorem / School of Mathematics, Georgia Institute of Technology
[book] M. Moore / 2006 / Four Color Theorem / Department of Mathematical Sciences, University of Arkansas
[web] I. Cahit / The Four Color Theorem and Three Proofs / http://www.emu.edu.tr/~cahit/TheFourColorTheorem-ThreeProofs.html
[web] K. Brown / The Four Color Theorem / http://www.mathpages.com/home/kmath266/kmath266.htm
[web] E. W. Weisstein / The Four-Color Theore / Wolfram MathWorld / http://mathworld.wolfram.com/Four-ColorTheorem.html
[journal] K. Appel / 1977 / Every Planar Map is Four-Colorable, Ⅱ : Reducibility / Illinois Journal of Math 21 : 491~567
[journal] M. Gardner / 1975 / Mathmatical Games: On Tessellatings the Plane with Convex Polygons / Science American 232 : 112~117
[book] S. Wagon / 1999 / Mathematica in Action, 2nd Ed / Springer-Verlag : 535~536
[confproc] S. Wagon / 2002 / A Machine Resolution of a Four-Color Hoax / Proceedings of the 14th Canadian Conference on Computational Geometry : 174~185
[journal] A. B. Kempe / 1879 / On the Geographical Problem of the Four Colors / American Journal of Math 2 : 193~200
[journal] P. J. Heawood / 1898 / On the Four-Color Map Theorem / Quart. Journal Pure Math 29 : 270~285
[journal] N. Robertson / 1996 / A New Proof of the Four-Colour Theorem / Electronic Research Announcements of the American Mathematical Society 2(1)
[web] A. Dharwadker / A New Proof of the Four Colour Theorem / http://www.geocities.com/dharwadker/
[web] A. Dharwadker / The Vertex Coloring Algorithm / http://www.geocities.com/dharwadker/vertex_coloring/
[web] Wikipedia / Degree (Graph Theory) / Wikimedia Foundation Inc / http://en.wikipedia.org/wiki/Degree_(graph-theory)
[web] Wikipedia / Hadwiger-Nelson Problem / Wikimedia Foundation Inc / http://en.wikipedia.org/wiki/Hadwiger_Nelson_Problem
-
171 Viewed
Print this page
Download PDF