Define G as a simple loopless maximal planar graph.
Remove a vertex (v) with degree = 8 from graph G.
The resulting subgraph is graph (G-v);
G R Y
1----2----3
| |
5---------4
B R
Figure 1
The cycle graph (C) in Figure 1 is an induced subgraph of both G and of (G-v),
and consists of the 5 neighbors of v. If v is replaced in C and connected to every vertex in C, then graph G is recovered.
The colorability of G depends upon the coloring of C and the coloring of (G-v) The
objective is to determine the conditions necessary to make 4 <(Chi)G < 6
A If C is 3-colorable and (G-v) is 4-colorable; then G is 4-colorable
B If C is 4-colorable, but not 3-colorable, and (G-v) is 4-colorable;
then G is NOT 4-colorable
C If C is NOT 4-colorable, then (G-v) is not 4-colorable. , and G is
not 4-colorable.
Obviously, C must be 4-colorable unless something is done to (G-v) to make
C not 4-colorable! What? (G-v) is maximized by the addition of two interior
chords of C. This also offers the opportunity to configure C_max (C + 2 chords)
so that initially it is not properly colored. This is better examined relative
to a specific case.
G R Y
1----2----3
| |
5---------4
B R
Figure 2
.
If Figure 2, graph C has been assigned a typical 4-coloring which reflects Case B
above. This 4-coloring of C extends to a 4-coloring of (G-v) It is stipulated that a
3-coloring of C cannot extend to a 4-coloring of (G-v); because then G would be
4-colorable.
, then C must be 4-colorable and not 3-colorable. If C is 3-colorable,
then G is 4-colorable. If C is not 4-colorable, then G is not 5-colorable!
G is an mce if and only if C is 4-colorable but not 3-colorable whenever
(G-v) is 4-colorable. If C is 3-colorable, then Chi(G) > 4 only when (G-v)
is not 4-colorable. Then G is not minimal, and therefore not an mce.
If C is 3-colorable when (G-v) is 4-colorable, then Chi(G) < 5.
(G-v) is not a maximal planar graph! (G-v) can be maximized in to graph H
by adding two internal chords to C. H is smaller than G because it has fewer
vertices. If Chi(H) > 5 then G qualifies as an mce. However, if Chi(H) > 4,
then G is not minimal and is not an mce!
Let C_max be C with two interior chord. Then (H) is 4-colorable if and only
C_max is 3-colorable or 4-colorable. If C-max is not 3- or 4-colorable, then
H is not 4-colorable. This is based on the a priori presumption that Chi(G) > 4.
To maximize (G-v) into H we must add two edges (interior chords). These two edges
can be added any where we choose as long as they do not intersect each other.
If an edge was added between v_2 and v_4, then C
(for the moment) is not properly 4-colored. If C cannot be recolored to
re-establish 4-colorability, then Chi(H) > 4 and G cannot be minimal.
The next few paragraph explore what can happen when edge E_(24) is added.
G B Y
1--2--3
| \ |
| \|
5-----4
B R
Figure 2
One way to make Graph C 4-colorable is to recolor from R to B. At this point
we are not concerned with the possibility that v_2 cannot be recolored. We are
merely discussing the various ways of restoring 4-colorability to C.
G B Y
1--2--3
| / \ |
|/ \|
5-----4
B R
Figure 3
Now we can add E_(25) which makes C improperly colored.
If we had recolored v_4 = G, then we could add E_(14) to gum up the works.
If both v_2 and v_4 can be recolored at the same time, then a 3-coloring is avail-
able for C. We wonder, "How can one vertex be recolorable and not the other?"
A third possible recoloring is v_4 = B & v_5 = Y as in Figure 4
G R Y
1--2--3
| \ |
| \|
5-----4
Y B
Figure 4
Now if we want to mess with the coloring of C, we must first remove E_(24) before
adding E_(35). After E_(35); C will revert to the coloring of Figure 1.
Time for some more "what if's".
What if the recoloring in Figure 4 cannot be achieved? Praise the Lord.
What if the recoloring in Figure 4 can be achieved? Then we wonder;
"We have colorings {GRYRB} and {GRYBY}! Why can't we have a coloring
of {GRYRY}?"
In general, there are many possible, if not probable, 4-colorings. In every
case it is always possible to add an edge between two vertices with the same
color.
If only vertex is recolored, then after 20 recolorings, C will have the same
color scheme that it started with.
Forcing 4-colorability on a 5 node cycle graph is not easy, Such a graph itself
is 3-colorable. If there are only external chords and no internal chords, then
3-colorability is still available. Some unknown external configuration is
necessary. If G is a candidate for "minimalness", then external chords are
possible, but not very probable. This is mostly due to the 5-degree minumum for
every vertex.
Without internal and external chords, the only known technique to force two
disjoint vertices to have different colors is a "Kempe" chain!
It requires a minimum of four chains to force 4-colorability on a 5-vertex
cycle graph wth no chords. Two chains will fix the colors of three vertices
(with respect to each other). say v_1, v_3 & v_4. V_2 & v_5 cannot have
a common chain as five vertices can support only two Kempe chains. Therefore,
v_2 and v_5 must each be forced by an independent and unterminated chain. These
chains are not the same as a terminated chain which alternates two colors. the
independent chain is;
R R R
Y---B---Y---B---Y---B---Y ...
G G G
1 2 3 5 6 7 8 ...
The vertices is set(2) consist of all of the vertices that are neighbors of
either set (1) or set (3). {R B G} means that all vertices in set (2)must be
R, B or G. To insure this, all of the vertices in set(3) must be Y.
(1
Note that if v_5 were Y rather than B, then Figure 1 would be 3-coloring!
Why cannot v_5 be Y? One reason is that there is a B-Y Kempe chain betweem
v_3 and v_5. But what if no such chain was present? Then v_5 cannot be Y,
if and only if at least one of its neighbors is Y. Consider the chain below
5----6----7----8----9----10----11----12--- ... -- v_i(nfinity)
B Y ? Y ? Y ? Y Y
Figure 2
V_5 cannot be Y because its neighbor v_6 is Y
V_6 can be Y because is neighbor v_7 cannot be Y because v_7's neighbor v_8 is Y
V_8 can be Y because is neighbor v_9 cannot be Y because v_9's neighbor v_10 is Y
V_10 can be Y because is neighbor v_11 cannot be Y because v_11's neighbor v_12 is Y
ad infinitum!
If it happens that Figure 2 is a B-Y Kempe chain between v_5 & v_3, the intervening
odd numbered vertices would be B. But if the chain does not terminate, the colors
of the odd vertices are probably immaterial?
Figure 2 shows the last [or is it the first] vertex v_i is Y. But there is no way to force v_i to be Y because there is no v_(i+1) or v_(i+2). If v_i is not Y, then the
whole chain breaks down and v_5 can be colored Y!
The 5-cycle graph can have only two Kempe chains. These two chains can force three
or four vertices. The chains essentially force the three/four vertices to have three
different colors. The other two vertices must be forced by some other mechanism.
But there is no other viable mechanism. Consider some examples
Chains {13} & {14}: V-1, v-2 & v-3 are three different colors, v_4 may be the
same color as v_2. V_5 can be the same color as v_3.
Chains {24} & {25}: V-2, v-4 & v-5 are three different colors, v_1 may be the
same color as v_4. V_3 can be the same color as v_5.
Chains {13} & {35}: V-1, v-3 & v-5 are three different colors, v_2 may be the
same color as v_5. V_4 can be the same color as v_1.
Chains {14} & {24}: V-1, v-2 & v-4 are three different colors, v_3 may be the
same color as v_1. V_5 can be the same color as v_2.
Chains {25} & {35}: V-2, v-3 & v-5 are three different colors, v_1 may be the
same color as v_3. V_4 can be the same color as v_2.
These are the five possible chain pairs. None of the five pairs alone can force
the required 4-coloring of Figure 2.
Let's ponder some more on the difficulties of making a vertex (V)take on a specific
color (R) when two colors (R,G) are available.
First divide the vertices into sets.
Set S_1 contains all of the vertices that are neighbors of V
Set S_2 contains all of the vertices that are neighbors of the vertices in Set_1
Set S_3 contains all of the vertices that are neighbors of the vertices in Set_2
Set S_4 contains all of the vertices that are neighbors of the vertices in Set_3
Set S_i contains all of the vertices that are neighbors of the vertices in Set_(i-1)
Set S_n contains all of the vertices that are neighbors of the vertices in Set_(n-1)
Set S_1 must contain at least one G vertex (V_1) More than one G vertex in S_1
is immaterial as it only takes one G to deny G to V. Therefore, it is necessary
only to make sure that V_1 can be G. This can be done by ascertaining that V_1 has
no G neighbors is S_2. This is accomplished if all of V_1's neighbors in S_2,
themselves have G neighbors in S_3.
The inference here is that the odd numbered sets each need at least one G vertex.
Then the even numbered sets cannot have a G vertex that would deny G to the lower
even numbered set
Conclusion: All of the odd-numbered sets must have at least one G vertex.
Since, the graph has a finite vertics, the sequence of sets will eventually termin-
atr. It may terminate on a even set or on an odd set. The terminating set can
have no more than 3 vertices If odd, then one of the terminating vertices must be
G. But with only 3 vertices, the color G can neither be forced or prohibited.
Set S_2 cannot contain a combination of G vertices that would deny G to all S_1 vertices. This is possible only if all S_2 vertices have G neighbors in S_3
Set S_3 must contain a combination of G vertices that would deny G to all S_2 vertices.
This is possible if none of the vertices in S_3 have G neighbors in S_4
We know that if we want v_k to be R, we
must give it G, B and Y neighbors, but no R neighbors. We must make sure that the
neighbors of the neighbors of v_k include no R vertices.