We propose a feasible solution to the map coloring problem based on the Welsh- Powell algorithm and supplement it with a mathematical proof that it can find the approximate optimal feasible solution with O(n^2) time complexity.