Peter,

thank you for making me aware of this nice function FindVertexColoring[]! Somehow it had escaped my attention that with this one can create a four color map on just any subdivided area easily:

(* just some strcture to play with: *)
pts = First /@ MeshPrimitives[DiscretizeRegion[Disk[], MaxCellMeasure -> .004], 0];
meshReg = VoronoiMesh[pts]

lines = MeshPrimitives[meshReg, 1];
polygs = MeshPrimitives[meshReg, 2];
polyassoc = AssociationThread[Range[Length[polygs]], polygs];

(* function to convert a polygon into a list of lines: *)
polygsToLines[polygon_] := Line /@ Partition[#, 2, 1, 1] & @@ polygon

(* pairs of neighbouring polygons (they share the same line): *)
ppairs = ParallelTable[Select[polyassoc, ContainsAny[polygsToLines[#], {l, Reverse /@ l}] &], {l, lines}];
ppairs = Select[ppairs, Length[#] == 2 &];
udes = UndirectedEdge @@@ (Keys /@ ppairs);
graph = Graph[udes]

colors = FindVertexColoring[graph, {Red, Green, Yellow, Orange}];
colorRules = MapThread[Rule[#2, #1] &, {colors, VertexList[graph]}];
coloredPolygs = KeyValueMap[{#1, #2} &, Association@ppairs] /. colorRules;
Graphics[{coloredPolygs, lines}, ImageSize -> Large]

Very nice - and reminds a bit of stained glass, isn't it ?!? Regards -- Henrik