Using　a　small　quantity　of　DNA　molecules　and　little　experimental　time　to　solve　complex　problems　successfully　is　a　goal　of　DNA　computing.　Some　NP-hard　problems　have　been　solved　by　DNA　computing　with　lower　time　complexity　than　conventional　computing.　However,　this　advantage　often　brings　higher　space　complexity　and　needs　a　large　number　of　DNA　encoding　molecules.　One　example　is　graph　coloring　problem.　Current　DNA　algorithms　need　exponentially　increasing　DNA　encoding　strands　with　the　growing　of　problem　size.　Here　we　propose　a　new　DNA　algorithm　of　graph　coloring　problem　based　on　the　proof　of　four-color　theorem.　This　algorithm　has　good　properties　of　needing　a　relatively　small　number　of　operations　in　polynomial　time　and　needing　a　small　number　of　DNA　encoding　molecules　(we　need　only　6R　DNNA　encoding　molecules　if　the　number　of　regions　in　a　graph　is　R).