Possibly, although I was vaguely worried that doing so might introduce some sort of non-generality in the resulting graphs which might detract from the fun of the puzzle in some obscure way.

I think you're right, it probably would. I don't think I'd have the brain to work it out, but some people certainly would.

Another thing along the same lines would be to try to find a way of dividing a one-region one-coloured graph recursively with recolouring until you were bored. That would be a general approach (as an arbitrary graph could be assembled into such a hierarchy) if you could find out a recolour step, but trying to develop your own analytic algorithm for four-colouring is not something to do in your spare time, ;).

Fwiw, I implemented a four-colouring algorithm for work a couple of years ago and used the obvious recursive approach, but N was small.