본문 바로가기
  • Home

A Polynomial Time Algorithm for Vertex Coloring Problem

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2011, 16(7), pp.85-94
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Sang-Un, Lee 1 MyeongBok Choi 1

1강릉원주대학교

Accredited

ABSTRACT

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 .

Citation status

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