Re:Graph Coloring, or Proof by Crayon
by ColinWright on Tuesday December 18, 2012 @04:38PM
(#4939730)
It is true under the convention that we color each contiguous region the same color, and each contiguous region can get any color. It is pretty clearly not true if you insist that non-contiguous regions must be colored the same, which is what happens with enclaves.
This latter case is covered by the more abstract version of vertex coloring general graphs, which started with the four color conjecture by Guthrie in the late 1800's, but continues to this day with things like register coloring in compilers, schedule coloring in timetabling, and with the knowledge that graph three (vertex) coloring is NP-Complete.
This latter case is covered by the more abstract version of vertex coloring general graphs, which started with the four color conjecture by Guthrie in the late 1800's, but continues to this day with things like register coloring in compilers, schedule coloring in timetabling, and with the knowledge that graph three (vertex) coloring is NP-Complete.