title: DNA solution of a graph coloring problem.
abstract: The graph-theoretic parameter that has probably received the most attention over the years is the chromatic number. As is well-known, the coloring problem is an NP-Complete problem. In this paper, it has been solved by means of molecular biology techniques. The algorithm is highly parallel and has satisfactory fidelity. This work shows further evidence for the ability of DNA computing to solve NP-Complete problems.
authors.affiliation: Department of Mathematics and Physical Science, Nanhua University Hengyang, Hunan, 421001 P. R. China. liuyachun65@263.net
authors.forename: Yachun
authors.initials: Y
authors.lastname: Liu
authors.forename: Jin
authors.initials: J
authors.lastname: Xu
authors.forename: Linqiang
authors.initials: L
authors.lastname: Pan
authors.forename: Shiying
authors.initials: S
authors.lastname: Wang
mesh_terms: D001483:Base Sequence; D019295:Computational Biology; D004247:DNA; D008969:Molecular Sequence Data
chemical_list: D004247:DNA