Re:Graph Coloring, or Proof by Crayon
by ColinWright on Tuesday December 18, 2012 @04:59PM
(#4939835)
In mapping, enclaves are usually colored the same as the "parent" country to which they belong. It's an additional restriction that's actually well catered for in the generic graph coloring context, as opposed to the "map" coloring of the original problem (which did not bother with the enclave issue).
I believe his claim is that one country has 4 disconnected regions. If you have that and can only use one graph node to represent all of the disconnected regions then the adjacency graph isn't necessarily planar.
The traditional 4-color map rule only says that each neighboring region has a different color, not that the colors are meaningful.