Although you can start with a bulls-eye of concentric ring-countries; once you start making enough of these isthmuses into the centre, then some of those countr

Although you can start with a bulls-eye of concentric ring-countries; once you start making enough of these isthmuses into the centre, then some of those countries must be broken up into "arc-islands". You are correct that O(N) colours are needed if all the islands of one ring-country must have the same colour. But to encode that constraint graph-theoretically you would need "bridges" (edges) over isthmuses, which would make the thing non-planar.