본문 바로가기
  • Home

The Four Color Algorithm

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2013, 18(5), pp.113-120
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교 멀티미디어공학과

Accredited

ABSTRACT

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, denotingas , 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.

Citation status

* References for papers published after 2022 are currently being built.