@article{ART001771880},
author={Sang-Un, Lee},
title={The Four Color Algorithm},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2013},
volume={18},
number={5},
pages={113-120}
TY - JOUR
AU - Sang-Un, Lee
TI - The Four Color Algorithm
JO - Journal of The Korea Society of Computer and Information
PY - 2013
VL - 18
IS - 5
PB - The Korean Society Of Computer And Information
SP - 113
EP - 120
SN - 1598-849X
AB - 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.
KW - Minimum Vertex Cover (MVC);Maximum Independent Set (MIS);Minimum Degree;Chromatic Number
DO -
UR -
ER -
Sang-Un, Lee. (2013). The Four Color Algorithm. Journal of The Korea Society of Computer and Information, 18(5), 113-120.
Sang-Un, Lee. 2013, "The Four Color Algorithm", Journal of The Korea Society of Computer and Information, vol.18, no.5 pp.113-120.
Sang-Un, Lee "The Four Color Algorithm" Journal of The Korea Society of Computer and Information 18.5 pp.113-120 (2013) : 113.
Sang-Un, Lee. The Four Color Algorithm. 2013; 18(5), 113-120.
Sang-Un, Lee. "The Four Color Algorithm" Journal of The Korea Society of Computer and Information 18, no.5 (2013) : 113-120.
Sang-Un, Lee. The Four Color Algorithm. Journal of The Korea Society of Computer and Information, 18(5), 113-120.
Sang-Un, Lee. The Four Color Algorithm. Journal of The Korea Society of Computer and Information. 2013; 18(5) 113-120.
Sang-Un, Lee. The Four Color Algorithm. 2013; 18(5), 113-120.
Sang-Un, Lee. "The Four Color Algorithm" Journal of The Korea Society of Computer and Information 18, no.5 (2013) : 113-120.
