Given an undirected graph

the vertex coloring problem is to assign a different color for vertex mutually adjacent.This problem is an NP-complete one and has no effective solving method.But Adleman

[1]

introduced firstly the DNA computing in 1994

with which the NP-complete problems are likely to be solved.DNA-based algorithm simulates molecular biology structure of DNA by means of molecular biology technological computation.This paper first introduces the DNA algorithm for the vertex coloring problem based on bio-molecular technology.The key of the algorithm is coding for the vertex and the color of the vertex The problem is solved by tube operation that performs the basic core processing and extraction that makes the results visible.On the basis of the experimental bio-molecular method

the algorithm is an ef

fective method.Finally

the advantage and disadvantage are discussed

and the future research directions are pointed out.