Abstract: Adleman  showed that deoxyribonucleic acid (DNA) strands could be employed towards calculating solutions to an instance of the Hamiltonian path problem (HPP). Lipton  also demonstrated that Adlemanís techniques could be used to solve the Satisfiability problem. In this paper, we use Adleman-Lipton model for developing a DNA algorithm to solve Maximum k-colourable Sub graph problem. In spite of the NP-hardness of Maximum k-colourable Sub graph problem our DNA procedures is done in a polynomial time.
Keywords: DNA computing, NP-hard problem, Maximum k-colourable Sub graph problem