Molecular solutions for the Maximum K-colourable Sub graph Problem in   Adleman-Lipton model
  Adleman showed that deoxyribonucleic acid DNA strands could be employed towards calculating solutions to an instance of the Hamiltonian path problem . Lipton also demonstrated that Adleman 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. 
Akbar Moazzam, Babak Dalvand
cs.DS cs.ET