@article{ART001573805},

author={Sang-Un, Lee and MyeongBok Choi},

title={A Polynomial Time Algorithm for Vertex Coloring Problem},

journal={Journal of The Korea Society of Computer and Information},

issn={1598-849X},

year={2011},

volume={16},

number={7},

pages={85-94}

TY - JOUR

AU - Sang-Un, Lee

AU - MyeongBok Choi

TI - A Polynomial Time Algorithm for Vertex Coloring Problem

JO - Journal of The Korea Society of Computer and Information

PY - 2011

VL - 16

IS - 7

PB - The Korean Society Of Computer And Information

SP - 85

EP - 94

SN - 1598-849X

AB - The Vertex Coloring Problem hasn't been solved in polynomial time, so this problem has been known as NP-complete. This paper suggests linear time algorithm for Vertex Coloring Problem (VCP). The proposed algorithm is based on assumption that we can't know a priori the minimum chromatic number for graph . This algorithm divides Vertices of graph into two parts as independent sets and cover set , then assigns the color to . The element of independent sets is a vertex that has minimum degree and the elements of cover set are the vertices that is adjacent to . The reduced graph is divided into independent sets and cover set again until no edge is in a cover set . As a result of experiments, this algorithm finds the perfectly for 26 Graphs that shows the number of selecting is less than the number of vertices .

KW - Minimum Vertex Cover (MVC);Maximum Independent Set (MIS);Minimum Degree ();Vertex Coloring Problem;Chromatic Number ()

DO -

UR -

ER -

Sang-Un, Lee and MyeongBok Choi. (2011). A Polynomial Time Algorithm for Vertex Coloring Problem. Journal of The Korea Society of Computer and Information, 16(7), 85-94.

Sang-Un, Lee and MyeongBok Choi. 2011, "A Polynomial Time Algorithm for Vertex Coloring Problem", Journal of The Korea Society of Computer and Information, vol.16, no.7 pp.85-94.

Sang-Un, Lee, MyeongBok Choi "A Polynomial Time Algorithm for Vertex Coloring Problem" Journal of The Korea Society of Computer and Information 16.7 pp.85-94 (2011) : 85.

Sang-Un, Lee, MyeongBok Choi. A Polynomial Time Algorithm for Vertex Coloring Problem. 2011; 16(7), 85-94.

Sang-Un, Lee and MyeongBok Choi. "A Polynomial Time Algorithm for Vertex Coloring Problem" Journal of The Korea Society of Computer and Information 16, no.7 (2011) : 85-94.

Sang-Un, Lee; MyeongBok Choi. A Polynomial Time Algorithm for Vertex Coloring Problem. Journal of The Korea Society of Computer and Information, 16(7), 85-94.

Sang-Un, Lee; MyeongBok Choi. A Polynomial Time Algorithm for Vertex Coloring Problem. Journal of The Korea Society of Computer and Information. 2011; 16(7) 85-94.

Sang-Un, Lee, MyeongBok Choi. A Polynomial Time Algorithm for Vertex Coloring Problem. 2011; 16(7), 85-94.

Sang-Un, Lee and MyeongBok Choi. "A Polynomial Time Algorithm for Vertex Coloring Problem" Journal of The Korea Society of Computer and Information 16, no.7 (2011) : 85-94.