Efficient DNA Algorithms for Chromatic Number of Graph Problems

Xikui Liu and Yan Li
College of Information Engineering, Shandong University of Science
and Technology, Qingdao 266510, P.R. China

Abstract

Adleman's successful solution of a seven-vertex instance of the NP-complete Hamiltonian directed path problem by a DNA algorithm initiated the field of bimolecular computing. The graph-theoretic parameter that has probably received the most attention over the years is the chromatic number. The coloring problem is an NP--Complete problem. We provide DNA algorithms based on the molecular biology techniques to compute the vertex chromatic number of a given graph. The algorithms determine not merely the existence of a solution but yield all solutions (if any). The algorithm is highly parallel and has satisfactory fidelity. This work represents further evidence for the ability of DNA computing to solve NP-Complete problems.