I think jes5199 and I have observed the same phenomenon : by starting from a 3-country map and adding countries one by one in such a way that they touch as many already-added countries as possible, you'll always be able to colour the new country. The problem is: not every planar graph can be constructed in this way! Simple counterexamples are a dodecahedron and a Rubik's cube (which are planar topologically).

So if I ever had some time to spare on it, what I'd try is finding a set of construction operators for colored graphs that only add or substitute subgraphs, preserve colours, and can produce every planar graph.

See also the two color theorem.