@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.