Re: A determininistic four-coloring algorithm.


bill wrote:
Matt Zellman wrote:
Given any finite planar vertex-colored graph, there is a method that
can be used to reliably color the graph using four colors without
backtracking or testing multiple solutions. We will use the color set
A= {0,1,2,3}. We will define the boundary color set B= {1,2,3}. The
method is as follows:

1. Fully triangulate the graph by adding either edges or vertices (it
doesn't really matter, but adding edges will be easiest.)

2. Select any arbitrary region (which now has three vertices) in the
graph.

3. Color those three vertices 1, 2, and 3.

4. Continue coloring any adjacent vertices using only these three
colors, according to the following rules:

a. Let C be the set of colors adjacent to the vertex. If C does not
contain exactly two elements, then move on to the next vertex.

b. Let U be the number of disconnected uncolored regions adjacent to
the selected vertex. U can be calculated by counting the number of
transitions made from a colored vertex to an uncolored vertex as each
adjacent vertex is checked before returning to the starting vertex. If
U is not equal to 1, then move on to the next vertex.

c. If C contains two elements, the vertex should be colored the color
in B that is not in C.

5. When no more colorings can be made according to step 4, begin
coloring the vertices for which C contains three elements and U = 1,
according to the following procedure:

a. The Edges of the boundary of the selected vertex are defined by
the two vertices that are adjacent to uncolored vertices. They will
always be one of the two sets: S={1,1},{2,2},{3,3} or
D={1,2},{1,3},{2,3}, given that the specific elements of the set are
arbitrarily assigned, and the only important information is whether the
two vertices are the same color or not.

b. If the edges are of set D, then identify a Kempe chain of colors D
that connects the two vertices (if none exists, proceed to step 5c).
Assign the vertex to be defined the color 0. Finally, reverse the
complementary Kempe chain (containing the point just defined) that is
bounded by the one just identified, of colors D.

c. If no Kempe chain of colors D can be found connecting the two edge
vertices, find the Kempe chain of colors D that exists on either edge
vertex, and reverse it. Then, if the number of Elements in C is 2,
repeat step 4c for the given vertex; otherwise, proceed to step 5d.

d. If the edges are of set S, then identify a Kempe chain that
contains the color S and any one other color that connects the two edge
vertices. Assign the vertex to be defined the color 0, then reverse the
Kempe chain containing that point which is complementary to, and
bounded by, the one just identified.

e. Repeat step 4.

6. When no more colorings can be made according to step 5, there is
exactly one uncolored vertex remaining. Color the last vertex 0.

7. Finally, remove any edges or vertices added in step one, to return
the graph to its original configuration, retaining the colors of all
vertices still in the graph.

This procedure will reliably color any planar vertex-colored graph (and
its corresponding face-colored graph), with no more than four colors.
The reasoning behind this is that the algorithm above always leaves the
colored region with a boundary of no more than 3 colors. This means
that a new vertex can always be colored using the fourth color without
introducing any inconsistency, and then reversed using Kempe's method
to return the boundary (now extended) to no more than three colors.
Vertices can be added in this way indefinitely.

Step 5c may require some explanation. The case in which no Kempe chain
can be found between the edge vertices is the case in which the
complementary Kempe chain bisects the graph. The solution, then, is to
reverse one of the edge chains so that the colors of the two edges
match, and a path can necessarily be found between the two. This will
never raise the number of boundary colors above 3, because 0 is not a
possible element in set D (set D is necessarily a subset of set B).
Furthermore, this will always resolve the situation, because if the
change in color changes the number of elements in C to 2, then the
vertex can be colored the color in B that is not in C. On the other
hand, if the change in color does not change the number of elements in
C, then a Kempe chain will exist that crosses the one that previously
bisected the graph. For example, if our bisecting chain was of colors
{1,0} and our edge vertices are now both color 2, then a Kempe chain of
colors {1,2} will be able to cross the bisecting chain, and a chain
must exist between the two edge vertices. In the suspicious case that a
chain still does not exist after the first transformation, the same
resolution can be used to cross the second chain as the original chain,
until no barrier chains exist.

This indication follows from the fact that the initial coloring is
arrived at by coloring the system with only 3 colors from a central
region ("central" is a loose term here; since a finite planar graph
is isomorphic is a sphere, any region can be considered central).

The operation "move on to the next vertex" is undefined, because
the designation of the "next" vertex is arbitrary. Certainly a
deterministic mechanism for assigning the next vertex would make for a
more direct execution and probably a faster execution, but the
algorithm works for even totally random designations of the next
vertex.

The final vertex will always be able to be colored 0, because it is
adjacent to the entire boundary of the colored portion of the graph,
and thus is only adjacent to the colors in set B.

The "Kittell" graph is a famous and well known graph. Try to properly
4-color it using your method. If you can, I would consider that your
method is validated!

regards

---Bill J

That was one of the graphs I developed it on ;-) It was tested further
on the sciam hoax graph multiple times using various starting points
and sequences of vertices.

.

Quantcast