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.