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.