Citation
Instability in multicoloring and multiclique sequences

Material Information

Title:
Instability in multicoloring and multiclique sequences
Creator:
Sutorik, Sarah A
Publication Date:
Language:
English
Physical Description:
vii, 47 leaves : illustrations ; 29 cm

Subjects

Subjects / Keywords:
Graphic methods ( lcsh )
Graphic methods ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaf 47).
General Note:
Submitted in partial fulfillment of the requirements for the degree, Master of Science, Applied Mathematics.
General Note:
Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Sarah A. Sutorik.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
34376014 ( OCLC )
ocm34376014
Classification:
LD1190.L622 1995m .S88 ( lcc )

Downloads

This item has the following downloads:


Full Text
INSTABILITY IN MULTICOLORING
AND MULTICLIQUE SEQUENCES
by
Sarah A. Sutorik
A.A., Colorado Mountain College, 1982
B.S., University of Colorado at Denver, 1993
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Applied Mathematics
1995


This thesis for the Master of Science
degree by
Sarah A. Sutorik
has been approved
by
David C. Fisher
Kathryn Fraughnaugh
J. Richard Lundgren
Date


Sutorik, Sarah A. (M.S., Applied Mathematics)
Instability in Multicoloring and Multiclique Sequences
Thesis directed by Associate Professor David C. Fisher
ABSTRACT
The to-chromatic number Xm(G) of a graph G is the fewest colors needed so
each node has to colors and no color appears on adjacent nodes. Stahl has shown
that for any graph G, there is a p and k0 such that for the multicoloring sequence
Xi(G'), X2(G), X3(G),. . we have Xk+P(G) = Xk(G) + XP(G) for all k > k0. Stahl
dehned as chromatically unstable all graphs for which k0 > 0, and found the
first known such graph, Grotzchs graph, for which k0 = 1. Here we give several
other graphs which are chromatically unstable, including two for which k0 = 3.
Additionally, we examine the multiclique sequences of these graphs, finding that
most are cliquishly unstable as well.
This abstract accurately represents the content of the candidates thesis. I rec-
ommend its publication.
Signed_____________________
m
David C. Fisher


DEDICATION
To John Marriott
and
To Joseph and Jeanne Sutorik


CONTENTS
Figures .................................................................. vi
Tables ...................................................................vii
Chapter
1. Introduction .......................................................... 1
2. Instability in Multicoloring Sequences.................................. 7
2.1 Cycles ............................................................. 7
2.2 Mycielskians of Cycles ............................................. 8
2.2.1 Mycielskians of Even Cycles ....................................... 10
2.2.2 Mycielskians of Odd Cycles ........................................ 10
3. Instability in Multiclique Sequences .................................. 28
3.1 Cycles ............................................................ 28
3.2 Mycielskians of Cycles..............................................29
3.2.1 Mycielskians of Even Cycles ....................................... 29
3.2.2 Mycielskians of Odd Cycles ........................................ 30
References ............................................................... 47
v


FIGURES
Figure
1. The Mycielskian of C3 .................................................4
2. A 4-coloring of C43 with nine colors .................................. 9
3. 1-, 2-, and 3-colorings of fi(C3) ..................................... 11
4. One of 11 Type Z independent sets of n(Cn) ............................ 18
5. Type Y independent set of n(Cn) ....................................... 19
6. One of 11 Type X5 independent sets of n(Cn) .................... 21
7. One of 11 Type X3 independent sets of n(Cn) .................... 22
8. One of 11 Type X4 independent sets of n(Cn) .................... 23
9. 1-, 2-, and 3-cliques of fi(C3) .................................... 31
vi


TABLES
Table
1. The weight on each independent set in a k-coloring of //(C5) ...... 13
2. The weight on each independent set in a k-coloring of //(CV) ...... 14
3. The weight on each independent set in a k-coloring of fi(Cg) ...... 16
4. The weight on each independent set in a k-coloring of fi(Cu) ...... 26
5. The weight on each independent set in a k-coloring of //(C13) ...... 27
6. The weight on each node in a k-clique of //(C5) .................... 33
7. The weight on each node in a k-clique of /r(CV) .................... 37
8. The weight on each node in a k-clique of fi(Cg) .................... 42
9. The weight on each node in a k-clique of fi(Cu) .................... 46
vii


1 Introduction
A coloring of a graph G is a labeling of the nodes with 1, 2,. . ra, so that adjacent
nodes have different labels. Alternatively, it is easy to see but tedious to explain
that a coloring can be thought of as a collection of maximal independent sets such
that each node is in at least one set. The coloring number X(G) is the fewest
number of maximal independent sets in a coloring of G. Similarly, the k-coloring
number Xk(G) is the fewest maximal independent sets so that each node is in at
least k of the sets. The ^-coloring number may be found through the solution of
an integer program. Let K be the node maximal independence matrix of G, where
the rows of K represent the nodes of G and the columns represent all maximal
independent sets of G. If node i is in independent set j, then kij = 1; otherwise
kij = 0. Then Xk(G) is the value of the integer program:
Minimize lTx subject to Ax > kl,x > 0 and x integer, (1)
where 1 and 0 are vectors of all ones and all zeros, respectively, and x is a vector
such that Xj is the integer weight on independent set j. Since X(G) = X\(G),
this method also finds the value of X(G) by setting k = 1.
Fractional coloring is a generalization of coloring in that the weights on the
maximal independent sets need not be integer. The fractional coloring number
1


Xf(G) is the value of the linear program:
Minimize lTx subject to Kx. > 1, and x > 0. (2)
The problem of finding the chromatic number is dual to that of finding a
maximum clique. A clique of G is a complete subgraph of G. An alternative
definition is that a clique is a set of nodes such that each maximal independent
set of G contains at most one node of the set. The clique number lo(G) is the
maximum number of nodes in any clique of G. Expanding the idea, the k-clique
number u>k(G) is the largest sum of integer weights on the nodes so that the
sum of weights in any maximal independent set is at most k. The value of the
following integer program, where y is a vector such that zq is a weight on node z,
is tok(G)\
Maximize lTy subject to KTy < &l,y > 0 and y integer. (3)
The dual to the fractional coloring linear program (2) is the following:
Maximize lTy subject to KTy < 1, and y > 0. (4)
The value of (4) is the fractional clique number, cuj(G'), that is the largest sum of
(not necessarily integer) weights which may be placed on the nodes of G so that
for each maximal independent set, the sum of weights on that set is at most one.
Since (4) is the linear programming dual of (2), we have:
lo(G) < iUf(G) = Xf(G) < X(G). (5)
2


The fractional clique number and the ^-clique number are related in that a
maximal ^-clique may be transformed into a fractional clique by dividing the
weight on each node by k. Since this fractional clique may not be maximal,
^k_
which implies
uk(G) < [kuf{G)\ (6)
By similar reasoning,
MG) <
implying
MG) > \kXf(G)-} (7)
A graph construction which will be utilized heavily in this report is that of
Mycielski. Let G be a graph with nodes tq, n2,. ., vm. Then the Mycielskian y(G)
of G is the graph with nodes aq, aq,. ., xm, y\, j/2, , j/m, ^ with Xi adjacent to
Xj and y3 if and only if ry is adjacent to Vj in G] with yi adjacent to z for all i;
and no other edges. For example, the Mycieskian of C5 is illustrated in Figure 1.
Larsen, Propp, and Ullman [4] proved the following useful results for the
Mycielskian of any graph G:
u(fi(G)) = oj(G) (8)
X(y(G)) = X(G) + 1 (9)
3



Figure 1: The Mycielskian of C5.
4


*/MG = X/(G) + (10)
These results will be used extensively in later proofs, where we expand upon
several results by Stahl.
Stahl [5] showed that if a subadditive integer sequence (subadditive meaning
fi+m A fi + fm) has the property that y > y for some p and all /, then there
exists a k0 such that fk+p = fk + fP for all k > k0. Since an (/ + m)-coloring
may be formed from a minimal /-coloring and a minimal m-coloring, Xi+m(G) <
Xi(G) + Xm(G), and therefore the multicoloring sequence yi(G'), X2(GQ, X3(Cr),. .
is subadditive. If p is the least common denominator of a minimal fractional
coloring, then p times that fractional coloring is a p-coloring, so by (7), >
for some p and all k. Thus
p L
Xfc+p(Gr) = Xk(G) + Xp(G) for all k > ko} (11)
where p is the least common denominator of a minimal fractional coloring. There-
fore if k0 is known, we can find Xk(G) for all k in finite time.
For most common graphs, k0 = 0. Stahl [6] termed graphs for which k0 > 0
chromatically unstable, and published the first known example of such a graph.
The graph is known as Grotzchs graph, or alternatively, as p(Cs). The chromatic
stability number k0 of Grotzchs graph is 1.
Here we prove that several in the series of Mycielskians of odd cycles are
chromatically unstable, including two where the stability number is 3. Addition-
5


ally, we examine the multiclique sequences of this series of graphs, and find that
several are cliquishly unstable, meaning that k0 > 0 for the multiclique sequence
oo^(G), 002(G), 003(G),.... The highest clique stability number we have found com-
putationally is 18.
6


2 Instability in Multicoloring Sequences
Stahl [6] has shown that the Mycielskian of C5 has the property of chromatic
instability. We will show that the Mycielskians of C7, C9, Cn, and C13 have this
property as well.
2.1 Cycles
For completeness, we first show that all cycles are chromatically stable.
Theorem 2.1. For n even, Xk(Cn) = 2k.
Proof: For a ^-coloring of an even cycle, any two adjacent vertices require k
distinct colors each. Therefore, Xk(Cn) > 2k. But since an even cycle can be
^-colored by alternating between two sets of k colors as the cycle is traversed,
Xk(Cn) < 2k. Then for even cycles, Xk(Cn) = 2k for all k, and therefore even
cycles are chromatically stable.
Lemma 2.1. Xf(Cn) = for n odd.
Proof: An odd cycle contains n maximal independent sets of size n^~. So placing
a weight of on each node gives a fractional clique of weight Therefore,
Xf(Cn) > Additionally, since we can form a fractional coloring of an odd
cycle by placing a weight of on each of the n maximal independent sets,
7


Xf(Cn) <
The next theorem, showing odd cycles to be chromatically stable, is from
Stahl [5], although our proof is somewhat simpler.
Theorem 2.2. For n odd, Xk{Cn) = |"yzy]
Proof: Since Xk{G) > \kXf(G)~\, by Lemma 2.1, Xk(Cn) > [yzyj To show
Xk(G) < \kXf(G)~\, we hrst note that |"yzyj = 2k + 1 when & < |. Suppose
k < Then for n odd, we may Ucolor Ch with 2& + 1 colors as follows. Number
the vertices sequentially around the cycle, beginning with 1. Use numbers to
represent colors, and for each vertex i = 1,. . ,n, color vertex i with a set of
colors as follows:
1 + {k(i 1), k(i 1) + 1,..., ik l}(mod(2£; + 1)) if i < 2k + 1
< 1 to k if i > 2k + 1 and even
k + 1 to 2k if i > 2k + 1 and odd
For example, to 4-color C15 with nine colors, we would follow the above pro-
cedure to produce the result illustrated in Figure 2.
We have shown that Xk(G) = [yzyj for k < |. Now if k > |, then:
Xk{Cn) < Xn=l(Cn) + Xk_^n^}_^{Cn)
n 1
+
Mk (y1)
n 1
2 nk
n 1
Therefore, Xk(Cn) = [yzyj for n odd.
2.2 Mycielskians of Cycles
We now prove results regarding the chromatic stability of Mycieskians of cycles.
8


1234
Figure 2: A 4-coloring of C\$ with nine colors.
9


2.2.1 Mycielskians of Even Cycles
As with even cycles, the Mycielskians of even cycles have the property of chro-
matic stability.
Theorem 2.3. For n even, Xk(fi(G)) = |~yy]
Proof: Each n(Cn), n even, contains an induced 5-cycle. By Theorem 2.2, a
minimum ^-coloring of a 5-cycle requires |~yyj colors, therefore Xk(fi(Cn)) > |~y^j.
To show Xk(fi(Cn)) < |~yy] 5 we use a proof by induction. For n even, fi(Cn) {z}
is a bipartite graph, and hence, may be 1-colored with two colors. Coloring the
center with a third color shows that X\(ji(Cn)) < |"|j. Additionally, fi(Cn) {z}
may be 2-colored with four colors by coloring one partite set with the colors 1
and 2, and the other with colors 3 and 4. Now replace 1 and 3 on the inner nodes
by 5. Then the center may be colored by 1 and 3. Therefore, X2(fi(Cn)) < |~^y^j
For k > 2, assume Xfc_2(/u(C'n)) < |~^vy^l Then
Xk(j^(cn j) < Xk~2(jz(cn j) <
5(k 2)
2
+ 5
5 k
Y
Therefore, the Mycielskian of an even cycle is chromatically stable.
2.2.2 Mycielskians of Odd Cycles
Stahl [6] showed that fi(Cn) is chromatically unstable when n = 5. We will
show the same property holds when n = 7,9,11, and 13. Of special importance
is the fact that the chromatic stability number rises to three for n(Cn). For
10


completeness, we begin by showing that fi(C3) is chromatically stable.
Theorem 2.4. Xk(fJ,(C3)) = |~^pj for k = 1, 2, 3, ...
Proof: Since Xf(C3) = 3 and Xf(ji(G)) = Xf(G) + y 1 , we have Xf(ji(C3)) =
f. Then Xk(fi(C3)) > \kXf(C3)] = .
To show Xk(fj,(C3)) < |~^pj, we hrst illustrate that the inequality holds for
k = 1,2, and 3 by showing the appropriate Ucolorings in Figure 3.
ef
Figure 3: 1-, 2-, and 3-colorings of //((73).
Using induction, for k > 3, assume Xk-3(jJ>(C3)) <
M|. Then
Tfc(//(C'3)) < X/;_3(/i(C'3)) + X3(n(C3)) <
10(& -3)
3
+ 10
10A:
T
Therefore, Xk(fJ.(C3)) = |"^j for k > 1.
11


We now present examples of graphs which are chromatically unstable, begin-
ning with a proof of Stahls result for //(C5). We will use the following lemma.
Lemma 2.2. X4(ji(Cn)) = 4 for n odd.
Proof: Since the chromatic number of any odd cycle is 3, the result follows from
(9).
Theorem 2.5.
[ 4 for k = 1
WMC5)) = | otherwise
Proof: Since Xf(C5) = | and Xf(n(G)) = Xf(G) + y x. ., we have Xf(n(C5)) =
A f (Crj
Then Xk(n(C$)) > \kXj(C^)~\ = This lower bound holds for all k > 1.
However, for k = 1, Lemma 2.2 shows Xi{jjfCs)) = 4.
We now have only to show that Xk(ji(C$)) < for k > 1. This is done
with a proof by induction. For k = 2, 3, 10, and 11, Table 1 illustrates that the
inequality holds.
Furthermore, since Xk+i(G) < Xfc(Cr) + Xf G):
x^pfc^)) < x2(/i(c,5))
x^pfc^)) < x2(/i(c,5))
X^pfCz)) < X3 (jj,(C7))
Xri^pfG^f) < X^pfC^))
XsipfCs)) < X4(/i((75))
X^pfCz)) < X4(/i((75))
Thus, Xfc(//(C'5)) < |~^j for 2 < k < 11.
[^=121]. Then
Xfc(/i(C<5)) < Xfc_io(/i(C,5)) + Xio(/i(C,5
+ X2(/i((75)) = 12
+ X^pfC?))) = 15
+ X3AC5)) = 18
+ x^jjfCs)) = 21
+ X4(/i(C<5)) = 24
+ X5 (p)C^ ) ) = 27
For k > 11, assume X^-io (AC,)) <
"29(7; 10)" + 29 = "29 k
10 10
12


maximal k
independent sets 2 3 10 11
{mi, m3,7/1,2/3} 1 1 3 3
{m2, m4,2/2,2/4} 0 1 3 3
{m3, m5,2/3,2/5} 0 1 3 4
{m4, mi, 2/4,2/1} 1 1 3 3
{m5, m2,2/5,2/2} 1 1 3 3
{mi,m3,2:} 0 1 2 3
{m2,m4,2:} 1 0 2 2
{m3,m5,2:} 1 0 2 1
{m4,mi,2:} 0 1 2 2
{m5,m2,£} 0 1 2 3
{4, 2/1, 2/2, 2/4} 0 0 0 1
{2/1, 2/2, 2/3, 2/4, 2/5} 1 1 4 4
Xk{p{c$)) 6 9 29 32
Table 1: The weight on each independent set in a k-coloring of //(C5).
Therefore, Xk(fi(C5)) = for k > 1.
Theorem 2.6.
[ 4 for k = 1
WMCO) = | otherwise
Proof: Since Xf(C\) = |, and Xf(ji(G)) = Xf(G) + ^ , we have X/(/i(CV)) =
||. Then Xfc(//(CV)) > \kXy(//(C'7))~| = |"^pj This lower bound holds for all
k > 1. However, for k = 1, Lemma 2.2 shows that Xi(/i(CV)) = 4.
We now show that Xk(fi(Cr)) < fr & > 1- We will perform a proof
by induction. For k = 2, 3, 5, 6, 9, 13, 17, and 21, Table 2 illustrates that the
inequality holds.
Furthermore, since Xk+i(G) < Xk(G) + Xi(G):
13


maximal k
independent sets 2 3 5 6 9 13 17 21
{xux3,x5,yuy3,y5} 0 0 1 1 2 2 3 4
{^2? 3^4? ^6? U2'} V4t} ]Jo\ 0 0 1 1 1 2 3 4
{x3,x5,x7,y3,y5,y7} 0 1 1 1 1 3 3 4
^^4, Xg, y^i ij\\ 0 1 1 1 2 4 4 4
{x5,x7,x2,y5,y7,y2} 0 1 1 1 2 2 3 4
H H CO CO 1 0 1 1 2 2 3 4
{£7,£2,£4, y7,2/2,2/4} 1 0 1 1 2 2 3 4
{zi, £3,3:5 ,z} 1 1 1 1 1 3 3 3
{x2, x4, x6, zj 1 1 1 1 2 2 3 3
{x3,x5,x7 ,z} 0 0 1 1 2 0 2 3
{£4, X6, £1 ,zj 0 0 1 1 1 0 1 3
{x5,x7,x2,zj 0 0 0 1 1 2 2 3
{£6, £1, £3, zj 0 1 0 1 1 3 3 3
{x7, £2, £4, zj 0 1 1 1 1 3 3 3
{x5,x7,y2,y3,y5,y7} 1 0 0 0 0 1 1 0
{2/1, 2/2, 2/3, 2/4, 2/5, 2/6, 2/7} 1 2 2 3 4 5 7 9
Xk{y{C7)) 6 9 14 17 25 36 47 58
Table 2: The weight on each independent set in a k-coloring of y(C7).
14


X4(/i(C,7)) < X2(/i(C,7))
Xri( n(Cri)) < X2(/i(C,7))
Ts(+(CV)) < X2(/i(C,7))
Xio(+(CV)) < X5(+(CV))
Xll(+(CV)) < X5(+(CV))
Tl2 (+(TV ) ) < X&i^p^Gj))
Tl4(+(CV)) < X5 (h(TV))
Tl5 (+(TV ) ) < ^6 (+(CV ) )
Tl6(+(CV)) < Xri( n(Cri))
^18(A*(Cf7)) < Xg(+(CV))
Tig(+(CV)) < Tg(+(CV))
X2o(f^(Gti) ) < Tio(+(CV))
T22 (+(TV ) ) < Tg(+(CV))
Thus far, we have Xfc(//(CV)) < |"^fj
Xfc_2i(fJ.(C7)) < |~58(2i21)] Then
+ X2(+(CV)) = 12
+ X5 (+(CV)) = 20
+ = 23
+ X5(+(CV)) = 28
+ Xe(+(CV)) = 31
+ = 34
+ Tg(+(CV)) = 39
+ Tg(+(CV)) = 42
+ Xg(fJ,(Cr)) = 45
+ Xg(/J,(Cr)) = 50
+ Xw(^(Cr)) = 53
+ X\o( )) = 56
+ ^13(A*(Cf7)) = 61
2 < k <22. For k > 22, assume
58(k 21)
21
+ 58 =
58 k
~21
Tfc(+(CV)) < Xk-2i{^{Cr)) + X2i(+(CV)) <
Therefore, Xfc(//(CV)) = |"^fj for k > 1.
Theorem 2.7.
[ 4 for k = 1
U(MO = | otherwise
Proof: In a fashion similar to the previous theorem, we find that Xk(fi(Cg)) >
|W|- Since xf(C^) = l xf(XC9)) = Then Xk(fi(C9)) > \kXf(fi(C9))] =
|~^rj. But Xi(/u(C'g)) does not meet its lower bound of 3, since Lemma 2.2 shows
X1(fi(C9)) = 4.
To show Xk(fi(Cg)) < |~^rj for k > 1, we perform a proof by induction. For
k
= 2, 3, 4, 5, 7, 10, 23, and 36, Table 3 illustrates that the inequality holds.
Furthermore, since Xk+i(G) < Xk(G) + X/(Cr), we have:
15


maximal k
independent sets 2 3 4 5 7 10 23 36
{xux3,x5,x7,yuy3,y5,y7} 1 0 1 1 1 2 3 5
{^2? 3^4? ^6? ^8? U2'} 2/4? 2/6? 2/8} 0 0 0 1 1 1 4 5
{x3,x5,x7,x9,2/3,2/5, y7, y9} 0 0 0 1 1 1 3 5
{^4? Xg, Xg^ ^1? 2/4? 2/6? 2/8? 2/l} 0 0 0 0 1 1 3 5
{x5,X7,X9,X2,J/5,J/7,J/9,J/2} 0 1 0 0 1 1 3 5
^Xg, Xg, Xg^ 2/6? 2/8? 2/l? 2/3^ 1 1 1 1 1 1 3 5
{^7, 3?g, ^2? ^4 5 1J7} ]j9i 2/2 ? 2/4 } 1 1 1 1 1 1 3 5
{m8, mi, m3, m5, y8, yu y3, y5} 0 1 1 1 1 2 3 5
%2') ^4? 3?g, 2/95 2/2? 2/4? 2/6^ 0 1 1 1 1 2 3 5
{xi, x3, x5, x7, z} 0 2 0 1 1 0 2 4
3^4? 3?g, 3?g, 0 1 1 1 1 1 1 4
{x3, x5, x7} x9} zj 0 0 1 0 1 2 2 4
{^4, Xg, Xg, -S'} 0 0 1 0 1 2 3 4
{x5, x7, x9, x2, zj 0 0 1 1 1 2 3 4
H GO H H CO 0 0 0 1 1 2 3 4
{x7l x9, x2, x4, zj 0 0 0 0 0 1 3 4
{x8, X!,X3, X5, zj 1 0 0 0 0 0 3 4
^Xg, X2 1 ^4? 3?g, 1 0 0 1 1 0 3 4
{x3,x5,x7,yuy3,y5,y7,y9} 0 0 0 0 0 0 1 0
{m2, m4,2/2,2/4, J/6,2/r, 2/s, J/g} 0 0 0 0 0 1 0 0
{s/1,2/2,2/3, S/4,2/5,2/6, s/r, 2/s, 2/9} 1 1 2 2 3 4 10 16
Tfc(/i(6g)) 6 9 11 14 19 27 62 97
Table 3: The weight on each independent set in a k-coloring of fi(C9).
16


For k = 6, 8, 9, and 11:
Xk(p(Cgj) < X^p^Co,)) + Xk-4(p(Cgj) < 11 +
"97(7: 4)" '97k
36 36
For k = 12, 13, ..., 22, 24, 25, ..., 35, and 37:
Xk(p(Cgj) < Xio(p(Cgj) + Xfc_io(/i(C'g)) < 27 +
"97(7; 10)' '97k
36 36
Thus far, we have Xk(p(Cg)) < |~||j for 2 < k < 37. For k > 37, assume
Xfc-selMCh)) < [97(3~36)j. Then
Xk(p(Cgj) < Xfc_36(/i(C,9)) + X3e(p(Cgj) <
97(7; 36)
36
+ 97
97k
~36
Therefore, Xk(p(Cg)) < |"||j for all 7; > 37, and the proof is complete.
We continue to proofs of the chromatic instability of p(Cu) and p(C\z). Note
that the chromatic stability number has increased from 1 to 3.
Lemma 2.3. X3(/u(C'n)) = 9.
Proof: We first show that X3(/u(C'n)) > 9. Suppose not. Then we are able to
find eight independent sets of p(Cu) such that each node is included in at least
three sets. To color all twenty-three nodes with three colors each, we need at
least 23 3 = 69 node-colors total.
Label the nodes as before, with the outer nodes labeled ap through in, the
inner nodes y\ through j/n, and the center z. The largest independent set which
includes z is the type of set shown in Figure 4. We refer to this type of set as a
17


X
Figure 4: One of 11 Type Z independent sets of n(Cu)
18


Type Z independent set and notice that through rotation, there are eleven such
sets.
Three Type Z independent sets are required to 3-color z, providing at most
3 6 = 18 node-colors. We now require at most five additional independent sets
which together provide at least 51 node-colors.
The unique largest independent set of fi(Cu) is the one consisting of the eleven
inner nodes. Call this set a Type Y set, illustrated in Figure 5.
Figure 5: Type Y independent set of n(Cu).
At least one Type Y set must be used to provide 51 node-colors using five
19


independent sets. However, if more than one Type Y set is used, there are
three or fewer independent sets with which to color the outer nodes. Since any
independent set contains at most five outer nodes, these three independent sets
combined with the three independent sets of Type Z provide at most 3 5 + 3 5 =
30 node-colors on the outer nodes. But since the outer nodes require at least
3-11 = 33 node-colors, we must use exactly one of the Type Y independent sets.
We have used four independent sets, providing at most 18 + 11 = 29 node-
colors. So we must find four more independent sets which together provide at
least 40 node-colors. Since we can no longer use a Type Y set, the only type of
independent set containing eleven nodes, each of the four independent sets must
contain ten nodes, for a total of exactly 69 node-colors. In other words, each
node must be included in exactly three independent sets.
Each Type Z independent set provides five node-colors on the outer nodes.
Therefore, we need exactly 33 (3 5) = 18 more node-colors on the outer
nodes. There are two cases which satisfy this criteria. See Figures 6 through 8
for illustrations of the following types of independent sets.
Case 1: Three Type X5, one Type X3. One independent set of Type X3 col-
ors seven inner nodes. These nodes have been previously colored by an
independent set of Type Y, so each requires inclusion in exactly one more
independent set, a set of Type X5. Consider the four sequential inner nodes
20


of the Type X3 set. We require two distinct independent sets of Type X5 to
complete the 3-coloring of these four nodes. But then the last independent
set of Type X5 cannot be used without adding another color to at least one
of the four sequential inner nodes, an impossibility since each must have
exactly three colors.
Figure 6: One of 11 Type X5 independent sets of /u,(C\4).
Case 2i Two Type X3^ two Type X4. Any choice of the two independent sets
of Type X4 forces at least one inner node to be colored by both of these
21


Figure 7: One of 11 Type X3 independent sets of n(Cu).
22


X
Figure 8: One of 11 Type X4 independent sets of n(Cu).
23


independent sets. Call this node yr Since y3 was already 1-colored by the
independent set of Type Y, it is now 3-colored. Therefore, we cannot in-
clude y3 in either of the two Type X5 sets to be used. Then Xj will not be
included in a Type X5 set either, and therefore must have been colored by
three independent sets of Type Z. Consider xJ+1, which is adjacent to both
xj and yr Since Xj and y3 are colored by six distinct independent sets, we
would require three more distinct independent sets to color xJ+i, for a total
of nine, a contradiction of our hypothesis that y(C\\) can be 3-colored with
eight colors.
We have shown that X3(/u(C'n)) > 9. Table 4 illustrates that y(C\\) can be 3-
colored with 9 colors; therefore, X3(/u(C'n)) < 9.
Theorem 2.8.
MA.Cn)) <
4 for k = 1
9 for k = 3
otherwise
Proof: Similar to previous theorems, Xf(Cn) = y, which implies X f(y(G\i)) =
yr, and Xk(y(G\i)) > |~yyj But ^or k = 1 and 3, this lower bound is not met,
since Lemma 2.2 shows Xi(y(Cu)) = 4 and Lemma 2.3 shows X3(y(Cu)) = 9.
To show Xk(y(G\i)) < for k = 2, 4, 5, 6, . we perform a proof by
induction. For k = 2, 4, 5, 6, 7, 9, 29, 32, and 55, Table 4 illustrates that the
inequality holds. For k = 8, 10, 11, ..., 28, 30, 31, 33, 34, ..., 54, 56, and 57,
we have Xk(fJ.(Cu)) < X6(//(C'n)) + Xjt_6(//(C'n)) = .For k = 58, we have
24


^58(/^(Cll)) < ^29{fJ{Cll)) + X29{fl{Cii)) |"14gg58^j
Thus far, we have Xfc(/u(C'n)) < |~y|pj for k = 2,4, 5,. . 58. For k >
58, assume Xk-^p^Cn)) < [~ 146(g~55)]. Then Xfc(/u(C'n)) < Xjt_55(A(C'n)) +
X55(/u(C'n)) = for k > 58, and we are done.
Theorem 2.9.
4 for k = f
8 or 9 for k = 3
otherwise
Proof: Since Xf(C13) = ^, we have Xf(ji(C13)) = ySf and Xfc(/u(C'i3)) > .
Xfc(/i(C'i3)) <
Lemma 2.2 shows Xi(fi(Ci3)) = 4. Computational results have shown that
X3(jj>(C\3) = 9. However, at the time of this paper, a theoretical proof does
not exist. Table 5 shows X3(/u(C' 13)) < 9.
We prove Xk(ji(C\3)) < for k = 2, 4, 5, 6, ... by induction. For k = 2, 4,
5, 6, 7, 9, 11, 14, 19, 27, 35, and 78, Table 5 illustrates that the inequality holds.
For k = 8, 10, and 12, we have Xk{ji{C13)) < X6{ji{C13)) + Xjt_6(//(C'i3)) = .
For & = 54, 62, and 70, we have Xk(/j,(C13)) < X35(n(C13)) + Xk_35(/j,(C13)) =
|"22§fcj pQr ^ -y3 through 81 except 14, 19, 27, 35, 54, 62, and 70, we have
xk([i(Ci3j) < Xn(jA,(Ci3j) + X/;_ii(/i(C'i3)) =
For k > 81, assume Xfc_78(//(C'i3)) < ["205C~78)j, Then Xk((i(C13)) < Xfc_78(/u(C'i3)) +
X73{n(Ci3)) = for k > 81, and we are done.
25


maximal k
independent sets 2 3 4 5 6 7 9 29 32 55
{*1, x3, x5, x7, x9, y1, y3, y5, y7, y9} 0 0 0 1 0 1 1 3 3 6
^61 ^i0; y2i y4i ye, y8i y\o\ 1 0 1 1 1 1 1 3 3 6
{^3, ^5, ^7? %ih y3i y5-> y71 y*4^ y\\\ 0 0 1 1 0 1 1 4 3 6
{'£'4i %8i ^10; ^1; 2/4i 2/6? 2/8? 2/l0? 2/l} 0 1 1 1 0 0 1 3 3 6
{^5 ? ^7? ^9 ? ? ^2 ? 2/5 ? y7? 2/9? 2/11 ? y2} 0 1 0 1 1 0 1 3 3 6
{^6? x$^ ^10? ^1? %3i ye, 2/8? 2/10? 2/1? 2/3} 0 0 0 0 0 1 1 3 3 6
{%7i ^9 ? ^n? %2i %4i y71 2/9? 2/11? 2/2? 2/4} 1 0 0 0 0 1 1 3 3 6
{^8? ^1? %3-> ^5? 2/8? 2/10? yi ? 2/3? 2/5} 0 1 0 0 1 1 1 3 3 6
{^9? X\\^ %2-> %4i ^6? 2/9? 2/11? 2/2? 2/4? y&\ 0 1 1 0 1 0 1 3 4 6
{^10? ^1? %3i ^5? %7i 2/10? 2/1? 2/3? 2/5? 2/7} 1 1 1 1 1 1 1 3 3 6
{^11? %2-> %4i ^61 ^81 2/11? 2/2? 2/4? 2/6? 2/s} 0 0 0 1 0 1 1 3 5 6
{^1 ? ^3? ^5? ^7? ^9? 1 0 1 1 1 0 1 3 2 5
{X2-, ^£4? ^6? ^8? ^10? 0 0 0 1 0 1 1 2 4 5
{^3 ? X5, X'j, Xg, X\\^ Zj- 0 1 0 1 1 1 1 1 4 5
{^4? Xg, Xg^ ^10? ^1? £} 0 0 0 1 1 1 1 2 4 5
{^5 ? X'j, Xg, X2-, Zj- 0 0 0 1 0 1 1 3 4 5
{^6? ^8? ^10? ^1? ^3? 0 1 0 0 1 0 0 3 4 5
{^7? ^9 ? ^11 ? ^2 ? ^4 ? 0 1 1 0 1 1 0 3 4 5
{^8 ? ^io? ^1 ? ^?3 ? ^5 ? 0 0 1 0 0 1 1 3 3 5
{^9 ? 2^11 ? ? ^4 ? ^6 ? 0 0 0 0 0 0 1 3 2 5
{^10 ? ^1 ? ^3 ? ^5 ? ^7? 0 0 0 0 0 0 1 3 1 5
{^11 ? ^2? ^4? ^6? ^8? 1 0 1 0 1 0 1 3 0 5
{a?i, m3, x5, x7,2/1,2/3, y5, y7,2/9, 1/10} 0 0 0 0 0 0 0 0 2 0
{*1, *3, *5, *10,2/1,2/3,2/5,2/7,2/8,2/10} 0 0 0 0 0 0 0 0 1 0
{^1? ^6? ^8? ^10? 2/l? 2/3? 2/4? 2/6? 2/8? 2/lC)} 0 0 0 0 1 0 0 0 0 0
{^2? ^4? ^6? ^n? 2/2? 2/4? 2/6? y8i y9? yn} 0 0 0 0 0 1 0 0 0 0
{*3, *5, *7, *9, 2/1, 2/3, 2/5, 2/7, 2/9, 2/ll} 0 0 0 0 1 0 0 0 0 0
{^4, Xg, Xg, ; y2i y4i ysi y8i yio} 0 0 0 0 0 0 0 1 0 0
{x\^ ^3? ^6? %9i 0 0 0 0 0 1 0 0 0 0
{*2, *4, *11, 2/2, 2/4, 2/6, 2/7, 2/8, 2/9, 2/ll} 0 0 0 0 1 0 0 0 0 0
{2/1, 2/2, 2/3,2/4,2/5,2/6,2/7,2/8,2/9,2/10,2/11} 1 1 2 2 2 3 4 13 14 25
Tfc(/i(Cii)) 6 9 11 14 16 19 24 77 85 146
Table 4: The weight on each independent set in a k-coloring of /i((7n).
26


maximal k
independent se 2 3 4 5 6 7 9 11 14 19 27 35 78
-!>i >*3 ,*5 > *7 , x9 > *11 > 2/1 , 2/3 , 2/5 , 2/7 2/9, an} 1 1 0 0 0 0 1 1 1 1 3 3 7
-|>2. x^_, Ci> H! CO *10- *12 > 2/2 , 2/4 , 2/6 , 2/8 2/10 ai2 } 1 1 0 0 0 0 1 1 2 1 3 3 7
-!>3. *5 > x7>x9> *11> *13 > 2/3 , 2/5 , 2/7 , 2/9 2/11 ai3 } 1 1 0 0 0 0 1 1 0 1 3 3 7
{x4, *6 > *8> *10 > *12 > *1 > 2/4 , 2/6 , 2/8 , 2/10,2/12,2/1 } 0 1 0 0 0 1 1 1 1 2 2 3 7
-!>5. x7 > *9> *11 > *13 > *2 > 2/5 , 2/7 , 2/9 . an ai3. a2 } 0 0 0 1 1 1 1 1 1 2 2 4 7
}>6> *8 > *10 > *12 > X1 > *3 > 2/6 , 2/8 , 2/10, 2/12, 2/1, 2/3 / 0 0 0 1 1 1 1 1 0 2 2 3 7
-|>7> *9 > xll>x13>x2 , x4 > 2/7 , 2/9 . an. ai3. V2> yi} 0 0 0 1 1 1 1 1 0 2 2 3 7
}>8> *10 ,x12> *1> *3 , *5 > 2/8 , 2/10, 2/12, yi, 2/3,2/51 0 0 1 1 1 1 1 1 0 2 2 3 7
-|>9, *11 ,*13>*2>*4 , *6 > 2/9 , 2/11, 2/13, a2. a4. a6 } 0 0 1 1 1 1 1 0 2 2 2 3 7
{^10 Hi to Hi Hi CO > *7 > 2/10 > 2/12 > 2/1, a3.as.a7> 0 0 1 1 1 1 1 1 1 2 2 3 7
{^11 ,*13>*2>*4>*6 > *8 > 2/11, 2/13, 2/2, a4. a6. ys} 0 0 1 0 1 1 0 1 2 1 2 3 7
{x12,11,13,15,17 , *9 , 2/12, 2/1, 2/3, 2/5,2/7 a9> 0 0 1 0 0 1 0 1 1 1 2 3 7
{^13 >*2 , X4. Xfi > *8 > *10 , 2/13, 2/2, 2/4, 2/6,2/8 aio } 0 1 0 0 0 0 1 0 1 1 3 3 7
-!>i *3>*5>*7>*9>*11 2} 0 0 1 1 1 1 1 1 1 3 1 3 6
{x2 . *4> x6 x8, x10 , *12 , 2 1- 0 0 1 1 1 1 1 1 0 3 0 3 6
{x3 . *5>*7>xg,X41, *13 , 2 1- 0 0 1 1 1 1 1 0 1 2 0 3 6
t>4 . x6>x8>x10> *12 *1 , 2 1- 1 0 0 1 1 1 1 0 0 0 2 2 6
}>5 . X7 xq x-\ 1 , *13 *2 , 2 1- 0 1 0 0 0 0 1 1 0 0 3 1 6
{1-6 . x8>x10> *12 *1 *3 , 2 1- 0 0 0 0 0 0 0 1 3 1 3 2 6
-!>7> x9>X11> *13 *2 a?a , 2 1- 0 0 0 0 0 0 0 1 4 1 3 3 6
{1-8 . *10 > *12 *1 *3 *5 , 2 1- 0 0 0 0 0 0 1 1 2 1 3 3 6
{x9 . *11 > *13 *2 a; 4 *6 , 2 1- 0 0 0 0 0 1 0 1 0 0 3 3 6
{^10 *12 *1 *3 *5 *7 , 2 1- 0 0 0 0 0 0 0 1 0 0 3 3 6
{^11 *13 *2 x4 *6 *8 , 2 1- 0 0 0 0 0 0 1 1 0 2 3 3 6
{^12 ,xl, *3 > *5 , *7, *9 2 1- 0 2 0 0 1 1 1 1 1 3 2 3 6
{^13 x2 > *6, *8, *10 , z\ 1 0 1 1 1 1 1 1 2 3 1 3 6
-!>i x3 *5> *12 > 2/1 y3 2/5 2/7 2/8, 2/9, 2/10, ai2> 0 0 0 0 0 0 0 0 1 0 0 0 0
}>2> x4^, x6>x13 > 2/2 > 2/4 > 2/6, 2/8, 2/9, 2/10 2/11 ai3> 0 0 0 0 0 0 0 1 0 0 0 0 0
}>3 *5 x7 > x9 VI, V3> Vb > V7> V9> 2/11, 2/12, ai3> 0 0 0 0 0 0 0 0 0 0 1 0 0
{x4, x6 > x8>x10 ,V1, y 2> 2/4, 2/6, 2/8, 2/10 2/12 ai3> 0 0 0 0 0 0 0 1 0 0 0 0 0
}>5 x7 x9>X11> VI 2/2 2/3 2/5 2/7, 2/9, 2/11, ai3> 0 0 0 0 0 0 0 0 1 0 0 0 0
-!>i, x6 > *8>x10 > *12 > 2/1 , 2/3 , 2/4 , 2/6 , 2/8 2/10 ai2 } 0 0 0 0 0 0 0 0 1 0 0 1 0
}>2> x^j *6> *11 > *13 > 2/2 , 2/4 , 2/6 , 2/8 , 2/9 2/11 ai3 } 0 0 0 0 0 0 0 0 0 1 0 0 0
{x4, x6 > *8>x10 > *12 > 2/1 , 2/2 , 2/4 , 2/6 , 2/8 2/10 ai2 } 0 0 0 0 0 0 0 0 0 0 1 0 0
{1:5. *7> x9>X11 > *13 > 2/2 , 2/3 , 2/5 , 2/7 , 2/9 2/11 ai3 } 0 0 0 0 0 0 0 0 1 1 0 0 0
-!>i *10 ,x12> 2/1 > 2/3 > 2/4 2/5 2/6 2/7 2/8 2/10 ai2> 0 0 0 0 0 0 0 0 1 1 0 0 0
}>3 x5 > x7> yi> V3> Vb> V7> V9> V10> 2/11 2/12 ai3> 0 0 0 0 0 0 0 0 1 0 0 0 0
}>9 *11 , *13- V2> V3 > 2/4 2/5 2/6 2/7 2/9 2/11 ai3> 0 0 0 0 0 0 0 1 0 0 0 0 0
}>3 *5 > CO 2/5,2/7, y8> 2/9, yio> 2/11 2/12 ai3> 0 0 0 0 0 0 0 0 1 0 0 0 0
{y^ through I/! 3} 1 1 2 3 3 3 4 4 4 8 12 16 36

xfc(M(C13)) 6 9 11 14 16 19 24 29 37 50 71 92 205
Table 5: The weight on each independent set in a k-coloring of //(C13).
27


3 Instability in Multiclique Sequences
Mycielskians of odd cycles have provided interesting results in chromatic instabil-
ity. These graphs also prove to be useful in discovering instability in multiclique
sequences.
3.1 Cycles
We first show that all cycles are cliquishly stable.
Theorem 3.1. For n even, tOk{Cn) = 2k.
Proof: The Avclique number of a graph is the maximum total integer weight
which can be placed on the nodes so that each independent set has weight at
most k. An even cycle is a bipartite graph; therefore, since we cannot put a
weight of more than k on either partite set, u>k < 2k. But by placing a total
weight of k on the nodes of each partite set, we find a ^-clique, so u>k > 2k.
Therefore, every even cycle is cliquishly stable.
Theorem 3.2. For n odd, Uk(Cn) = [yzyj .
Proof: Since ujf(Cn) = Xj(Cn) = fr 11 odd, and uik < \_kivj\, we have
uk < [yzyj To show the converse, note that 2k = when k < |. If k < |,
then a Avclique of value 2k may be formed by placing a weight of k on each of two
28


adjacent nodes in the cycle. Therefore, for k < ^,Uk(G) > [yzyj So if k >
then:
Mk{Cn) > ^n=L(Cn) + UJk_^n=lj(Cn)
Therefore, all odd cycles are cliquishly stable.
MY1
n 1
)

+
2n(A--(Y) 2 nk
n 1 n 1
3.2 Mycielskians of Cycles
We now proceed to results regarding the cliquish stability of Mycielskians of
cycles.
3.2.1 Mycielskians of Even Cycles.
We show that Mycielskians of even cycles are cliquishly unstable.
Theorem 3.3. For n even, fi(Cn) = |^J .
Proof: For n even, fi(Cn) contains an induced 5-cycle. Since Uk(C^) = |^J,
we have Uk(fJ.(Cn)) > [ yJ We shw that Uk(fJ.(Cn)) < |^J through a proof by
induction. For n even, we may find a 1-clique of fi(Cn) with value 2 by assigning
a weight of 1 to each of two adjacent outer nodes. Additionally, we may find a 2-
clique of value 5 by assigning a weight of 1 to each of the following: two adjacent
outer nodes, say aq and aq+i, the corresponding inner nodes, jq and jq+i, and the
center node z. Therefore, when k = 1 or 2, we have u>k(fi(Cn)) < |^J For k > 2,
assume cu/;_2(/u(C'n)) < I AAA) I Then
^k{^{Cn)) A LOk 2 (h(FVi,) ) + ^2 {k{Cn)) A
5 (k 1)
2
+ 5
5 k
Y
29


Therefore, Mycielskians of even cycles are cliquishly stable.
3.2.2 Mycielskians of Odd Cycles
We begin by showing that for n = 3 and 5, we have that g(Cn) is stable in its
multiclique sequence. In the following proofs, we let cq,&q and c represent the
weights on nodes aq, jq, and z respectively. In addition, let a = a\ + a2 + + an,
and b = bi + b2 + + bn.
Theorem 3.4. uk(ji(C3)) = [^J
Proof: Since uf(g(C3)) = Xf(ji(C3)) = y, we have uk(ji(C3)) < [ kxf(fi(C3))\ =
. We show that Uk(/J,(C3)) > for k = 1,2, and 3 by presenting the
appropriate k-cliques in Figure 9.
For k > 3 assume u>k-3(fi(C3)) > I 10(^ 3) I Then by induction,
^k(^(C3)) > LOk-3(}l(C3)) i03(jj(C3)) >
10(A: 3)
+ 10 =
10 k
which concludes our proof.
Lemma 3.1. For k = 9 + 10h, where h > 0 and integer, < [qyj 1.
Proof: For k = 9 + 10h, we can algebraically show that [qyj 1 = 25 + 29h.
There are two cases.
Case 1: c > 4 + Ah. We have five independent sets of g(C3) of the form {aq, x3, z},
{x2, x4, z}, . {x5, x2, z}. Since a1 + a3 + c < 9 + 10h, a2 + a4 + c < 9 + 10h,
30


2
Figure 9: 1-, 2-, and 3-cliques of //(C3).
31


. ., a5 + a2 + c < 9 + 10h, we have that
Ci\ + (23 Ct2 + (24 (23 + (25 (24 + (24 (25 + (22 / 9 + 10h C
a = --------------1--------------1---------------1--------------1------------ < 5 --------------------
Additionally, the independent set {j/i, 2/2,2/3,2/4,2/5} has weight at most 9 +
10h. Therefore, summing the weights over all nodes:
45 50h 5
^9+10/1 (+(^5)) = a + b + c < ----------------h (9 + 10h) + c < 25 + 29h.
Case 2: c < 3 + Ah. Now we use independent sets of the form {24, x3, j/i, j/3},
{m2, m4,2/2, J/4}, , {5,2,J/5,J/2}- Since ai + a3 + 61 + 63 < 9 + 10 h,
(22 + (24 + 62 + 64 + 9 + 10h, . (25 + (22 + 65 + 62 + 9 + 10h, we have
( \\ , 7 , (al + &l) + (a3 + ^3) , (+2 + b2) + (+4 + ^4)
^9+10/i(/^(h5 )) a + o + c - I--------------
(+3 + ^3) + (+5 + b5) (a4 + 64) + (ai + bi) (a5 + 65) + (a2 + b2)
\ r ~Z r ~Z r C
. 9 + 10h .
< 5 | ^------I + c < 25 + 29h.
Therefore, for k = 9 + 10h, we have uj9+Wh{lJ>{C5)) < 25 + 29h = 1.
Theorem 3.5.
LOk(/A,(C5j)
1 lr k = 9 + 10h, h > 0 and integer
otherwise
Proof: Since uf(fi(C5)) = Xf(/A,(C5j) = f§, then uk(fi(C5)) < [kiof(G)\ = [qf J;
for k = 9 + 10h, Lemma 3.1 shows 1. To prove equality, we
use induction. For k < 10, Table 6 illustrates that equality holds.
32


k
nodes 1 2 3 4 5 6 7 8 9 10
x1 0 0 1 1 1 1 2 2 2 3
x2 0 0 0 1 1 2 2 2 2 3
x3 1 1 1 1 2 2 2 3 3 3
X4 1 1 1 1 2 2 2 3 3 3
x5 0 0 1 1 1 2 2 2 2 3
2/i 0 0 0 0 1 2 1 2 2 2
IJ2 0 1 1 1 2 1 1 2 2 2
V3 0 0 1 1 1 1 2 1 2 2
Vi 0 0 1 1 0 1 2 1 2 2
V5 0 1 0 1 1 1 1 2 1 2
z 0 1 1 2 2 2 3 3 4 4
ojk{y{C5)) 2 5 8 11 14 17 20 23 25 29
Table 6: The weight on each node in a k-clique of y(C3).
For k > 10, assume that the result holds for k 10. Then since Uk(y(C3)) >
Lok-w{y(C3)) + zjw(y(C3)) the result follows for k > 10.
We now present examples of graphs which are cliquishly unstable.
Lemma 3.2. u;3(//(CV)) < 7.
Proof: There are three cases.
Case 1: c > 2. There are seven independent sets of C7) of the form {aq, x3, x5, z},
{x2, x4, x6, z}, . {aq, x2, x4, z}. Since oq + a3 + a5 + c < 3, a2 + 4 + 6 + c <
3, . oq + a2 + a4 + c < 3, we have
a\ + a3 + a5 a2 + 4 + a6 ,
a = ----------------1---------------h
^07 + 02 + 04 ^ j
3 c
The independent set {y4, y2}. . y7} has weight at most 3, therefore ^(//(CV))
= a + b + c < 21~7c + 3 + c < 7.
33


Case 2: c = 0. Now we use independent sets of the form {aq, x3, x5, y1? y3} y5}}
{x2, x4, x6,2/2,2/4, ye), {x7, x2, x4, y7, y2, y4}. Since a4 + a3 + a5 + b4 +
b3-\-b3 N 3, a2 + <24 + <26 + b2 + b4 + b3 < 3, . ., 07 + a2 + 4 + ^7 + b2 + b4 < 3,
we have
( (r< w 1 7 1 (i + &i) + (3 + 63) + (5 + h)
u3{g{C7)) = a + b + c= ---------------------------------
(a2 + b2) + (a4 + 64) + (a,Q + 6g) , , (a7 + b7) + (02 + b2) + (04 + 64)
+----------------3---------------+'' +----------------5---------------+c
< 7.
Case 3: c = f. Each independent set of outer nodes {x4, x3, x5}, {x2, x4, x6},
. ., (x7, x2, x4} can have a total weight of at most 2, since including z in
each set forms a maximal independent set. So at least one node of each of
the above sets has weight 0. Since each node is in three of the above sets,
at least three of the outer nodes are weighted 0. We have two cases.
Case a: No two zero-weighted outer nodes are sequential. Then there must
be exactly three zero-weighted outer nodes. Without loss of generality,
suppose a4 = a3 = a5 = 0. Since a4- > 0 for i ^ 1,3,5, it follows that
(17 + a2 + a4 + c > 4. But since (x7, x2, x4, z} is an independent set, we have
(17 + a2 + a4 + c < 3, a contradiction.
Case b: Two of the zero-weighted outer nodes are sequential. With-
out loss of generality, suppose the two sequential nodes are x4 and x2.
34


Then all other nodes of //(CV) are contained in S = {x3, x5, xr, 2/3, j/5, 2/7} U
{x4, x6, j/i, 2/2, J/4,2/6} U {z}. But since S is the union of two maximal inde-
pendent sets and z, the total weight on the nodes of S is at most 3+3+1 = 7.
Therefore, u;3(//(CV)) < 7.
Lemma 3.3. For k = g + 21 h, where g = 4, 8, 20 and h a nonnegative integer,
^MCt)) < [+J 1.
Proof: Let qg represent an integer associated with each 5, where q4 = 2, q8 =
4, and 520 = 9- For k = g 21 h, we can show 1 = J + 58h 1. There
are two cases.
Case 1: c > qg + 9/j. Since a4 + a3 + a5 + c < g + 21/j, a2 + a4 + a6 + c < g + 21/j,
. ., ar + a2 + a4 + c < g + 21/j, we have
a = -----------------1-----------------1------1--------------- < 7 ----------------- .
Additionally, the independent set {2/1,2/2, , 2/7} has weight at most g-\-21h,
therefore:
, ,, 7 ^ 7g + 147 7c
^++21/1 (+(FV)) = a + 6+c < ------------\-(g-\-21 h)-\-c <
58^
21
+ 58/i-l.
Case 2: c + qg 1 + 9h. Since jj4 + jj3 + a§ + bi + 63 + 65 + g + 21 /j, a2 + jj4 +
a6 + ^2 + ^4 + bg < g + 21/j, . ., 07 + a2 + a4 + ^7 + ^2 + ^4 + g + 21/j, we
have
a + b + c
(a4 + 64) + (a3 + &3) + (05 + 65)
35


(a2 + ^2) + (a4 + ^4) + (a6 + bg) (a7 + b7) + (02 + ^2) + (+4 + ^4) ,
4--------------------------------------1----1------------------------------------he
_ /g + 21h\
<7 -- +c<
58^
21
+ 58h 1.
Therefore, for g = 4, 8, 20, we have iOk(g(C7)) = 023+2i/i,(/(CV)) < + 58h
1 = |^| 1.
Theorem 3.6.
7
tok(ji(C7)) =
for k = 3
1 fr & = g + 21/j, g = 4, 8, 20, h > 0 and integer
otherwise
Proof: Since ujf(fi(C7)) = X/(//(CV)) = we have uJk(g(C7)) < (/^(C'r))J =
. Lemma 3.2 shows u;3(//(CV)) < 7. By Lemma 3.3, iOk(g(C7)) < 1
for k = g-\-2lh and the given values of g. We use induction to show equality. For
k = 1, 2, 5, 6, 7, 10, 11, 12, 15, 16, and 21, Table 7 shows that equality holds.
For k = 3, 4, 8, and 9, we have
[^J 1 for k = 4,8
k-x(+(CV)) > ^2(+(CV)) + tOk-2{g{C7)) = <
[+rj for £ = 3, 9
For k = 13, 14, 17, 18, 19, 20, 22, 23, and 24, we have
k-x(+(CV)) > ^i2(+(CV)) + k+-i2(/^(CV)) <
^ I 1 for jfc = 20
otherwise
For k > 24, assume that the result holds for k 21. Since u>k(fi(C7)) >
cu/;_2i(/u(C'7)) + u;2i(/^(CV)), the result holds for k > 24.
36


k
nodes 1 2 5 6 7 10 11 12 15 16 21
x1 1 0 0 1 1 2 2 2 3 3 4
x2 1 0 1 1 2 2 2 3 2 3 4
x3 0 0 1 1 2 2 2 3 3 3 4
x4 0 1 1 1 1 2 2 2 3 3 4
x5 0 1 1 1 1 2 2 2 3 3 4
x6 0 0 1 1 1 1 2 2 3 3 4
x7 0 0 1 1 1 2 2 2 3 3 4
2/i 0 0 1 1 2 1 2 2 2 3 3
2/2 0 0 1 1 1 2 2 1 3 3 3
2/3 0 1 1 1 0 2 1 1 2 2 3
2/4 0 0 1 0 1 1 1 2 2 2 3
2/5 0 0 1 0 1 1 2 2 2 2 3
2/6 0 1 0 1 1 2 2 2 2 2 3
2/7 0 0 0 2 1 1 1 2 2 2 3
z 0 1 2 3 3 4 5 5 6 7 9
LOk(jl(C7)) 2 5 13 16 19 27 30 33 41 44 58
Table 7: The weight on each node in a k-clique of //(CV).
37


For the next two proofs, we will refer to types of maximal independent sets
of fi(Cg) as follows:
Type X3 : {x4, x3, x5,yu y3, y5, y7, y8}, {x2, x4, x6, y2,2/4,2/e, 2/s, 2/g}, ,
{m9, m2, m4, y9, t/2, 2/4,2/e, 2/r}
Type X4 : {x4, x3, x5, x7, yu y3, y5,2/r}, {2, x4, x6, x8, y2,2/4,2/e, 2/s}, - -,
"{+9, ^2, X4j Xq, 2/9, 2/2, //4, //6}
Type y : {2/1,2/2, - -, 2/9}
Type Z : {ap, x3, x5, x7, z}, {x2, x4, x6, x8, zj,. ., {x9, x2, x4, x6, zj
Lemma 3.4. ^(//(Cg)) < 12.
Proof: There are three cases.
Case 1: c > 3. There are nine Type Z independent sets of y(Cg). Since a4 +
o3 T $5 T o7 + c < 5, 02 T o4 + &q + o§ + c < 5, ..., 09 T (22 T o4 + &q T c + 5.
we have
04 T a3 T a5 T 07 02 + 04 + 06 + a8
a = ---------------------1---------:----------1-----h
09 + (I2 T a4 T Og
< 9
5 c
The Type Y independent set has weight at most 5, therefore io5(y(Cg)) =
o + 6 + c < + 5 + c < 12.
Case 2: c < 1. Using the Type X4 independent sets, since a4 + a3 + a5 + a7 +
61 + 63 + 65 + 67 < 5, 02 + o4 + 06 + og + 62 + b4 + b3 + 6s + 5, ...,
09 + 02 T o4 + 06 + 69 + 62 + 64 + 66 + 5, we have o + 6 + c +
9(|)+c<12.
38


Case 3: c = 2. Each Type Z independent set has weight at most 5, and therefore
contains at least one outer node of weight 0. Since each ay is an element of
four Type Z sets, there are at least three zero-weighted outer nodes.
Case a: Two zero-weighted outer nodes are sequential. For any two se-
quential outer nodes, there is one Type X4 and one Type X3 independent
set that together contain all nodes except z and the two sequential zero-
weighted outer nodes. Since each independent set is weighted at most 5,
for this case, io5(g(Cg)) < 12.
Case b: No two zero-weighted outer nodes are sequential. It is easy to show
that there exists but one arrangement of three nonsequential zero-weighted
outer nodes which does not violate a maximum weight of 5 on all Type
Z independent sets; that is, the three zero-weighted outer nodes must be
equally spaced around the cycle. All other outer nodes must be at least 1,
to avoid falling into Case a. But the non-zero-weighted outer nodes cannot
exceed 1, else we could find Type Z independent sets of weight greater than
5.
Each zero-weighted outer node is an element of a Type X4 independent set
which contains three one-weighted outer nodes; therefore, its corresponding
inner node has weight at most 2. If any inner node corresponding to a zero-
weighted outer node has weight 0, then all other nodes except the center
39


are contained in two Type X4 independent sets, and then io5(g,(C9)) <
5 + 5 + 2 = 12. If one inner node corresponding to a zero-weighted outer
node has weight 2, then investigation of the Type X4 independent sets
shows that the other two must have weight 1. Then to exceed a total
weight of 12 and to avoid exceeding a maximum weight of 5 on the Type
Y independent set, exactly one other inner node must have weight 1; but
all such placements result in a set of Type X3 with weight 6. Therefore, all
inner nodes corresponding to zero-weighted outer nodes must have weight
1.
The maximum weight on the Type Y independent set then dictates that
the remaining inner nodes have total weight 2, but any placement of the
additional weight results in a Type X4 independent set with weight 6.
Therefore, co5(g(C9j) < 12.
Lemma 3.5. For k = g+36/y where g = 3, 6, 13, 19, 26, 35, and h a nonnegative
integer, ujk(g(C9)) < [^J 1.
Proof: Let qg represent an integer associated with each g, such that q3 = 2, q6 =
3, +L3 = 6, q49 = 9, q26 = 12, and q35 = 16. For k = g + 36h, it can be shown that
1 = |_Wj + 97/j 1. There are two cases.
Case 1: c>qg-\-16h. Using the nine Type Z independent sets, since ai+a3+a5 +
tt7+c + g+36h, U2+n4+(2g+(2g+c + ^+36h, . ., a9-\-a2~\~a4~\~aQ~\~c F ^/+36h,
40


we have
Cl\ (13 ~\~ (1$ d'j Oj2 ^4 + &Q + &$ OjQ Oj2 $4 -|- CLq
< 9 ^ + _
Since the Type Y independent set has weight at most g + 36h, we have
^g+36h(l^(C9)) = a + b + c < 9s+32^4/l + (g + 36h) + c < |^^fj + 97h 1.
Case 2: c < qg 1 + 16h. Using the nine Type X4 independent sets, since
al + a3 + a5 + a7 + ^l + ^3 + ^5 + ^7 ^ g -\~ 36h, , (29 -)- (^2 T (24 l- (2g + 69 + 62 + ^4 + ^6 ^ g T 36h, we have
a23+36/i(/4(C,9)) = a + b + c < + 97h 1.
Therefore, for g = 3, 6, 13, 19, 26, 35, we have tOk(g(C9)) < + 97h f =
9111 1
21 1
Theorem 3.7.
12
tok{g{C9)) =
for k = 5
|_^J 1 for k = g + 36h, g = 3,6,13,19, 26, 35,
h > 0 and integer
|^J otherwise
Proof: Since uf(g(C9)) = Xf(g(C9)) = §f, then uk(g(C9)) < \_kuf(g(C9))\ =
. By Lemma 3.4, we have io5(g(C9)) < 12, and Lemma3.5 shows iOk(g(C9)) <
1 fr ^ = 9 + 36h and the given values of g. Induction will show equality.
For k = 1, 2, 7, 8, 9, 12, 15, 16, 22, 25, 29 and 36, Table 8 shows that equality
41


holds. For k = 3, 4, 5, 6, 10, 11, 13, 14, 17, 18, 19, 20, 23, 24, 26, 27, 30, 31, 33,
34, 35, 38, 39, and 40, we have
^k(l(C9j) > ^2{l{C9))-\-iOk-2{^{C9))
' HA
[ 36
<
I ilk.
I 36
1 for k = 3,6,13,19,26,35,39
otherwise
For k = 21, uk(fi(C9)) > u9(n(C9)) + lj12(h(C9)) = For k = 28, 32, 37,
and 41, tOk(ji(C9)) > tOi&(ji(C9)) + iOk_i&(}i(C9)) =
k
nodes 1 2 7 8 9 12 15 16 25 29 36
x1 1 1 1 1 2 1 2 3 3 4 5
x2 0 1 1 1 1 2 2 3 3 4 5
x3 0 0 1 1 1 2 2 2 3 4 5
x4 0 0 1 1 1 1 2 2 3 4 5
x5 0 0 1 1 1 2 2 2 3 4 5
x6 0 0 1 1 1 2 2 2 3 4 5
xr 0 0 1 1 1 1 2 2 3 4 5
x8 0 0 1 1 1 2 2 2 5 4 5
x9 0 0 0 1 2 2 2 2 5 4 5
2/i 0 1 0 1 0 2 2 1 4 4 4
2/2 0 0 1 0 1 1 1 1 3 3 4
2/3 0 0 1 1 1 1 1 2 3 3 4
2/4 0 0 1 1 1 2 1 2 3 3 4
2/5 0 0 1 0 1 1 1 2 3 3 4
2/6 0 0 1 1 1 1 2 2 3 3 4
2/7 0 0 1 1 1 2 2 2 3 3 4
2/8 0 0 0 1 2 1 2 2 1 3 4
2/9 0 1 1 2 1 1 3 2 2 4 4
z 1 1 3 4 4 5 7 7 11 13 16
0Jk{l{C9)) 2 5 18 22 24 32 40 43 67 78 97
Table 8: The weight on each node in a k-clique of fi(C9).
For k > 41, assume the result holds for k 36. Then since Uk(jJ>(C9)) >
Uk-9e{^{C9)) + io36(fi(C9))} the result holds for k > 41.
42


In the next two proofs, we refer to the following types of maximal independent
sets of n(C n)):
Type X4 : {x4, x3, x5, x7, yu y3, y5, y7, y9, y10}, {x2, x4, x6, x8, y2,2/4, ye, Vs, yio, 2/n},
. . {^n, X2 X4, Xq} 2/ll, 2/2, 2/4, 2/6, 2/8, J/9}
Type X5 : {mi, z3, x5, x7, xg, y4, y3, y5, y7, y9}, {x2, x4, x6, x8, x10,2/2,2/4,2/e, 2/s, 2/io},
. . "4X9, X2, ^4, ^6, ^8, Vs, V2, Va, Uq, y&\
Type Y : {j/i,2/2,..., 2/11}
Type Zv . {1, X 3, X 5, X 7, X 9, 2, ^4, ^6, ^8, ^10, , { ^9, ^2, ^4, ^6, ^8,
Lemma 3.6. uj5(y(C\ 1)) < 12.
Proof: There are three cases.
Case 1: c > 3. There are eleven Type Z independent sets of y(C44). Since
al + a3 + a5 + a7 + 9 + c ^ 5, a2 + 04 + 6 + a8 + a10 + c ^ 5, . ,
9 + a2 + 4 + 6 + 8 + c < 5, we have a < 11 The Type Y independent
set has weight at most 5, therefore uj5(y(Cn)) = a + 6 + c < 55~llc + 5 + c <
12.
Case 2: c < 1. Using the Type X5 independent sets, since ai + a3 + a5 + a7 + a9 +
b4 + b3 + 65 + 67 + 69 < 5, a2 + 04 + 6 + a8 + io + ^2 + b4 + b3 + 6s + ^10 ^ 5,
. . 09 + 2 + aA + a6 + a8 + bg + 62 + b4 + &6 + ^8 ^ 5, We have ^(//(Cn)) =
a + 6 + c < 11 + c < 12.
Case 3: c = 2. Each Type Z independent set must contain at least two outer
nodes with weight 0. Since each pair of outer nodes are contained in at
most four Type Z independent sets, and since some duplication may occur,
there are at least five zero-weighted outer nodes.
43


Case a: Two zero-weighted outer nodes are sequential. Then all other
nodes excluding the center are contained in the union of a Type X4 and a
Type X5 independent set. Then io5(g(C n)) <5 + 5 + 2 = 12 in this case.
Case b: No two zero-weighted outer nodes are sequential. Then the five
zero-weighted outer nodes must be spaced at least one apart. But since all
other outer nodes have positive weight, there exists a Type Z independent
set with weight larger than 5, a contradiction.
Therefore, io5(g(Cn)) < 12.
Lemma 3.7. For k = g + 55h, where g = 8, 14, 17, 23, 26, 34, 43, 49, 52, 54,
and h a nonnegative integer, uJk(/a(Cii)) < 1.
Proof: Let qg represent an integer associated with each g, such that q8 = 4, q44 =
7,^17 = 8,923 = 11,926 = 12,934 = 16,943 = 20,949 = 23,952 = 24 and q54 = 25.
For k = g + 55h, we have |^y|=J 1 = + 146h 1.
Case 1: c > qg + 25h. Since each Type Z independent set has weight at most
g + 55h, we have a < 11 ^9+55h-c^ ^ gjnce Type Y independent set has
weight at most g + 55h, we have iog+55fl(g(Cn)) = a + 6 + c < llg+655/l~llc +
(g + 55h) + c < [ffaj + 146h 1.
Case 2: c < qg 1 + 25h. Since each Type X5 independent set has weight
at most g + 55h, and each node is an element of five such sets, we have
^g + 55h{^{C44)) = a + 6 + C 44


Therefore, ^(/r(C'11)) < J + 58h 1 = |_f^J 1.
Theorem 3.8.
12
Uk(fJ-(Cu)) = <
for k = 5
17 or 18 for k = 7
x for k = g + 55/^ ^ = 14j !75 23, 26, 34,43,49, 52, 54,
h > 0 and integer
146fc
55
otherwise
Proof: We have iOk(g(Cnj) < \_kiOf(g(Cn))\ = Lemma 3.6 shows
lo5(h(Cn)) < 12. Computational results show that LOr(g,(Cn)) = 17, however, a
theoretical proof does not yet exist. Lemma 3.7 proves ujg+55h{l^{Cii)) < 1
for the values of g given above. By induction, we will show equality. For k = 1,
2, 9, 10, 11, 16, 19, 20, 25, 28, 37, 46 and 55, Table 9 shows that equality holds.
For k = 3, 4, 5, 6, 7, 8, 12, 13, 14, 15, 17, 18, 21, 22, 23, 24, 26, 27, 29 and 30,
we have
Uk(fJ-(Cu
^i|Mj x for k = 8,14,17,23,26
otherwise
146fc
55
For k = 31, 32, ..., 36, 38, 39, ..., 45, 47, 48,..., 54, 56, 57, ..., 62, we have
LOkigiCn j) > L02o{g{C\\))-\-LOk-20 (h(C'n))
^i|§fcj x for k = 34^ 43^ 49^ 52^ 54
[iff J otherwise
For k > 62, assume that the result holds for k 55. Since LOk(g(Cii)) >
iOk-55(g(Cii)) + ^55(/u(C'n)), the result holds for k > 62.
Additionally, computational results have shown that g(C\?,) is cliquishly un-
stable at k = 7, 9, and 18.
45


k
nodes 1 2 9 10 11 16 19 20 25 28 37 46 55
x1 1 1 1 1 2 1 2 3 2 3 4 5 6
x2 0 0 0 1 1 2 2 2 3 3 4 5 6
x3 0 0 1 1 1 2 2 2 3 3 4 5 6
x4 0 0 1 1 1 2 2 2 2 3 4 5 6
x5 0 0 1 1 1 2 2 2 3 3 4 5 6
x6 0 0 1 1 1 1 2 2 3 3 4 5 6
xr 0 0 1 2 1 2 2 2 2 3 4 5 6
x8 0 0 2 2 1 2 2 2 3 3 4 5 6
x9 0 0 1 1 1 1 2 2 3 3 4 5 6
xw 0 0 0 1 1 2 2 2 3 3 4 5 6
Xu 0 1 1 1 2 2 2 3 3 3 4 5 6
2/i 0 1 0 1 0 2 2 1 3 3 4 4 5
2/2 0 1 1 1 1 2 2 2 2 3 3 4 5
2/3 0 0 1 1 1 2 2 2 2 2 4 4 5
2/4 0 0 1 1 1 1 3 2 3 2 4 4 5
2/5 0 0 0 1 1 1 2 2 2 2 3 4 5
2/6 0 0 1 1 1 2 2 2 2 3 3 4 5
2/7 0 0 1 0 1 1 2 2 3 4 3 4 5
2/8 0 0 1 0 1 1 1 2 2 3 3 5 5
2/9 0 0 2 1 1 2 1 2 2 2 3 5 5
2/10 0 0 1 1 2 1 1 2 2 2 3 4 5
2/n 0 0 0 1 1 1 1 1 2 2 4 4 5
z 1 1 4 4 5 7 9 9 11 13 17 21 25
LOk{jl{Cu)) 2 5 24 26 29 42 50 53 66 74 98 122 146
Table 9: The weight on each node in a k-clique of //(Cn).
46


REFERENCES
E Fisher, D.C., Fractional Colorings with Large Denominators, to appear
in Journal of Graph Theory.
2. Fisher, D.C., Marchant, M.A., Ryan, J., A Column Generating Algorithm
for Finding Fractional Colorings of Random Graphs, Congressus Numer-
antium, 89: 245-253.
3. Fisher, D.C., Periodicities in Discrete Systems, preprint
4. Larsen, M., Propp, J., and Ullman, D., The Fractional Chromatic Number
of a Graph and a Construction of Mycielski to appear in Journal of Graph
Theory .
5. Stahl, S., n-tuple Colorings and Associated Graphs Journal of Combina-
torial Theory, (B)20 (1976) 185-203.
6. Stahl, S., n-tuple Colorings of the Grotzch Graph, preprint
47


Full Text

PAGE 1

INST ABILITY IN MUL TICOLORING AND MUL TICLIQUE SEQUENCES b y Sarah A.Sutorik A.A.,Colorado Moun tain College,1982 B.S.,Univ ersit yof Colorado at Den v er,1993 Athesissubmittedto the Univ ersit yofColorado atDen v er inpartial fulllmen t of therequiremen tsfor thedegreeof Masterof Science AppliedMathematics 1995

PAGE 2

Thisthesisfor theMasterof Science degreeb y Sarah A.Sutorik has beenappro v ed b y Da vidC.Fisher KathrynF raughnaugh J.Ric hardLundgren Date

PAGE 3

Sutorik,Sarah A.(M.S.,AppliedMathematics) Instabilit yinMulticoloringand MulticliqueSequences Thesisdirectedb yAssociateProfessor Da vidC.Fisher ABSTRA CT The m -c hromaticn um ber m ( G ) of a graph G is thefew estcolorsneededso eac hnodehas m colorsandnocolorappearsonadjacen tnodes. Stahlhassho wn thatforan ygraph G ,thereisa p and k 0 suc hthatforthem ulticoloringsequence 1 ( G ) ; 2 ( G ) ; 3 ( G ) ;:::; w eha v e k + p ( G )= k ( G )+ p ( G )forall k>k 0 Stahl dened as \c hromaticallyunstable" all graphs for whic h k 0 > 0, and found the rst kno wn suc hgraph, Gr otzc h's graph, for whic h k 0 =1. Herew egiv esev eral other graphs whic h are c hromaticallyunstable, including t w o for whic h k 0 = 3. Additionally ,w eexaminethem ulticli quesequencesofthesegraphs, ndingthat mostare \cliquishlyunstable" as w ell. This abstract accurately represen ts the con ten t of the candidate's thesis. I recommenditspublication. Signed Da vidC.Fisher iii

PAGE 4

DEDICA TION T o JohnMarriott and T o Josephand JeanneSutorik

PAGE 5

CONTENTS Figures ::::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::: vi T ables ::::::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::::::::: vii Chapter 1. In troduction ::::::::::::::::::::::::::::::::::::::::::::::::::: ::::::::: 1 2. Instabilit yinMulticoloringSequences :::::::::::::::::::::::::::::::::::: 7 2.1 Cycles ::::::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::: 7 2.2 Mycielskiansof Cycles ::::::::::::::::::::::::::::::::::::::::::::::: 8 2.2.1 Mycielskiansof Ev enCycles :::::::::::::::::::::::::::::::::::::::: 10 2.2.2 Mycielskiansof OddCycles :::::::::::::::::::::::::::::::::::::::: 10 3. Instabilit yinMulticliqueSequences :::::::::::::::::::::::::::::::::::: 28 3.1 Cycles ::::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::: 28 3.2 Mycielskiansof Cycles :::::::::::::::::::::::::::::::::::::::::::::: 29 3.2.1 Mycielskiansof Ev enCycles :::::::::::::::::::::::::::::::::::::::: 29 3.2.2 Mycielskiansof OddCycles :::::::::::::::::::::::::::::::::::::::: 30 References ::::::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::::: 47 v

PAGE 6

FIGURES Figure 1. TheMycielskianof C 5 ::::::::::::::::::::::::::::::::::::::::::::::::::: 4 2. A4-coloring of C 15 with ninecolors :::::::::::::::::::::::::::::::::::::: 9 3. 1-,2-, and3-colorings of ( C 3 ) ::::::::::::::::::::::::::::::::::::::::: 11 4. Oneof11 T ype Z independen tsetsof ( C 11 ) ::::::::::::::::::::::::::: 18 5. T ype Y independen tset of ( C 11 ) :::::::::::::::::::::::::::::::::::::: 19 6. Oneof11 T ype X 5 independen tsetsof ( C 11 ) :::::::::::::::::::::::::: 21 7. Oneof11 T ype X 3 independen tsetsof ( C 11 ) :::::::::::::::::::::::::: 22 8. Oneof11 T ype X 4 independen tsetsof ( C 11 ) :::::::::::::::::::::::::: 23 9. 1-,2-, and3-cliquesof ( C 3 ) ::::::::::::::::::::::::::::::::::::::::::: 31 vi

PAGE 7

T ABLES T able 1. Thew eigh ton eac hindependen tsetina k-coloringof ( C 5 ) :::::::::::: 13 2. Thew eigh ton eac hindependen tsetina k-coloringof ( C 7 ) :::::::::::: 14 3. Thew eigh ton eac hindependen tsetina k-coloringof ( C 9 ) :::::::::::: 16 4. Thew eigh ton eac hindependen tsetina k-coloringof ( C 11 ) :::::::::::: 26 5. Thew eigh ton eac hindependen tsetina k-coloringof ( C 13 ) :::::::::::: 27 6. Thew eigh ton eac hnode inak-cliqueof ( C 5 ) ::::::::::::::::::::::::: 33 7. Thew eigh ton eac hnode inak-cliqueof ( C 7 ) ::::::::::::::::::::::::: 37 8. Thew eigh ton eac hnode inak-cliqueof ( C 9 ) ::::::::::::::::::::::::: 42 9. Thew eigh ton eac hnode inak-cliqueof ( C 11 ) :::::::::::::::::::::::: 46 vii

PAGE 8

1 In troduction A c oloring ofagraph G isalabelingofthenodeswith1 ; 2 ;:::;m ,sothatadjacen t nodes ha v edieren tlabels. Alternativ ely ,itiseasytoseebuttedioustoexplain thatacoloringcanbethough tofasacollectionofmaximalindependen tsetssuc h that eac h node is in at least one set. The c oloring numb er ( G ) is the few est n um berofmaximalindependen tsetsinacoloringof G Similarly ,the k-c oloring numb er k ( G ) isthefew estmaximalindependen tsets sothat eac hnode isinat least k ofthesets. The k -coloringn um berma ybefound throughthesolutionof anin tegerprogram. Let K bethe no demaximalindep endenc ematrix of G ,where the ro ws of K represen t the nodes of G and the columns represen t all maximal independen tsets of G If node i is inindependen tset j ,then k ij =1; otherwise k ij =0. Then k ( G ) isthev alueofthein tegerprogram: Minimize 1 T x subjectto K x k 1 ; x 0 and x in teger ; (1) where 1 and 0 arev ectorsofallonesandallzeros,respectiv ely ,and x isav ector suc h that x j is the in teger w eigh t on independen t set j Since ( G ) = 1 ( G ), thismethodalsonds thev alueof ( G ) b ysetting k =1. F r actional c oloring is a generalization of coloring in that the w eigh ts on the maximalindependen t sets need not be in teger. The fr actional c oloring numb er 1

PAGE 9

f ( G ) isthev alueof thelinearprogram: Minimiz e 1 T x subjectto K x 1 ; and x 0 : (2) The problem of nding the c hromatic n um ber is dual to that of nding a maxim umclique. A clique of G is a complete subgraph of G An alternativ e denition is that a cliqueis a set of nodes suc h that eac h maximalindependen t set of G con tains at most one node of the set. The clique numb er ( G ) is the maxim umn um berofnodes inan ycliqueof G Expanding theidea,the k-clique numb er k ( G ) is the largest sum of in teger w eigh ts on the nodes so that the sum of w eigh ts in an y maximalindependen t set is at most k The v alue of the follo wingin tegerprogram,where y isav ectorsuc hthat y i isaw eigh tonnode i is k ( G ): Maximize 1 T y subjectto K T y k 1 ; y 0 and y in teger : (3) Thedual tothefractionalcoloring linearprogram(2) isthefollo wing: Maximize 1 T y subjectto K T y 1 ; and y 0 : (4) Thev alueof(4)isthe fr actionalclique numb er f ( G ),thatisthelargestsumof (notnecessarilyin teger)w eigh tswhic hma ybeplacedon thenodesof G so that foreac hmaximalindependen tset,thesumofw eigh tsonthatsetisatmostone. Since(4) isthelinearprogrammingdual of(2),w eha v e: ( G ) f ( G )= f ( G ) ( G ) : (5) 2

PAGE 10

The fractional clique n um ber and the k -clique n um ber are related in that a maximal k -clique ma y be transformed in to a fractional clique b y dividing the w eigh ton eac hnode b y k Sincethisfractionalcliquema ynotbe maximal, f ( G ) k ( G ) k ; whic himplies k ( G ) b k! f ( G ) c (6) Bysimilarreasoning, f ( G ) k ( G ) k ; implying k ( G ) d k f ( G ) e (7) A graph construction whic h will be utilized hea vily in this report is that of Mycielski. Let G beagraphwithnodes v 1 ;v 2 ;:::;v m Thenthe Mycielskian ( G ) of G is the graph with nodes x 1 ;x 2 ;:::;x m ;y 1 ;y 2 ;:::;y m ;z with x i adjacen t to x j and y j if and only if v i is adjacen t to v j in G ; with y i adjacen t to z for all i ; andnootheredges. F orexample,theMycieskianof C 5 isillustratedinFigure1. Larsen, Propp, and Ullman [ 4 ] pro v ed the follo wing useful results for the Mycielskianof an ygraph G : ( ( G ))= ( G ) (8) ( ( G ))= ( G )+1 (9) 3

PAGE 11

v z v x 2 v y 2 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v x 3 v y 3 p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p ppp ppp ppp ppp ppp ppp pp ppp ppp ppp ppp ppp ppp ppp pp ppp ppp ppp ppp ppp ppp ppp pp ppp ppp ppp ppp ppp ppp ppp pp ppp ppp ppp ppp ppp ppp ppp pp ppp ppp ppp ppp ppp ppp ppp pp ppp ppp ppp ppp ppp ppp ppp pp ppp ppp ppp ppp ppp ppp ppp pp ppp ppp ppp ppp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v x 4 v y 4 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v x 5 v y 5 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v x 1 v y 1p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p Figure1: TheMycielskianof C 5 4

PAGE 12

f ( ( G ))= f ( G )+ 1 f ( G ) (10) These results will be used extensiv ely in later proofs, where w e expand upon sev eralresultsb yStahl. Stahl[ 5 ]sho w edthat ifasubadditiv ein tegersequence(subadditiv emeaning f l + m f l + f m ) has the propert y that f l l f p p for some p and all l then there exists a k 0 suc h that f k + p = f k + f p for all k > k 0 Since an ( l + m )-coloring ma ybeformedfromaminimal l -coloringand a minim al m -coloring, l + m ( G ) l ( G )+ m ( G ),andthereforethe multic oloring se quenc e 1 ( G ) ; 2 ( G ) ; 3 ( G ) ;::: is subadditiv e. If p is the least common denominator of a minim al fractional coloring,then p timesthat fractional coloringis a p -coloring, so b y(7), k ( G ) k p ( G ) p forsome p and all k Th us k + p ( G )= k ( G )+ p ( G ) for all k k 0 ; (11) where p istheleastcommondenominatorofaminim alfractionalcoloring. Thereforeif k 0 iskno wn,w ecan nd k ( G ) forall k innitetime. F or mostcommongraphs, k 0 =0. Stahl [ 6 ] termedgraphs for whic h k 0 > 0 chr omatic ally unstable and published the rst kno wn exampleof suc h a graph. Thegraphiskno wnasGr otzc h'sgraph,oralternativ ely ,as ( C 5 ). The chr omatic stability numb er k 0 of Gr otzc h'sgraph is1. Here w e pro v e that sev eral in the series of Mycielskians of odd cycles are c hromaticallyunstable,includingt w owherethestabilit yn um beris3. Addition5

PAGE 13

ally ,w eexaminethem ulticli quesequencesofthisseriesofgraphs, andnd that sev eralare cliquishly unstable meaningthat k 0 > 0 for the m ulticl iquesequence 1 ( G ) ;! 2 ( G ) ;! 3 ( G ) ;:::: Thehighestcliquestabilit yn um berw eha v efoundcomputationallyis18. 6

PAGE 14

2 Instabilit y in Multicoloring Sequences Stahl [ 6 ] has sho wn that the Mycielskian of C 5 has the propert y of c hromatic instabilit y W ewillsho w that the Mycielskiansof C 7 ;C 9 ;C 11 ; and C 13 ha v ethis propert yas w ell. 2.1 Cycles F orcompleteness,w erstsho w that allcyclesarec hromaticallystable. Theorem 2.1. F or n even, k ( C n )=2 k Proof: F or a k -coloring of an ev en cycle, an y t w o adjacen t v ertices require k distinct colors eac h. Therefore, k ( C n ) 2 k But since an ev en cycle can be k -colored b y alternating bet w een t w o sets of k colors as the cycle is tra v ersed, k ( C n ) 2 k Then for ev en cycles, k ( C n ) = 2 k for all k and therefore ev en cyclesarec hromaticallystable. 2 Lemma2.1. f ( C n )= 2 n n 1 for n o dd. Proof: Anoddcyclecon tains n maximalindependen tsetsofsize n 1 2 Soplacing a w eigh t of 2 n 1 on eac h node giv esa fractional cliqueof w eigh t 2 n n 1 Therefore, f ( C n ) 2 n n 1 Additionally since w e can form a fractional coloring of an odd cycle b y placing a w eigh t of 2 n 1 on eac h of the n maximal independen t sets, 7

PAGE 15

f ( C n ) 2 n n 1 2 The next theorem, sho wing odd cycles to be c hromatically stable, is from Stahl[ 5 ],although ourproof issomewhatsimpler. Theorem 2.2. F or n o dd, k ( C n )= l 2 nk n 1 m : Proof: Since k ( G ) d k f ( G ) e b y Lemma 2.1, k ( C n ) l 2 nk n 1 m : T o sho w k ( G ) d k f ( G ) e w e rst note that l 2 nk n 1 m = 2 k +1 when k < n 2 Suppose k< n 2 Thenfor n odd,w ema y k -color C n with2 k +1colorsasfollo ws. Num ber the v ertices sequen tially around the cycle, beginning with 1. Use n um bers to represen t colors, and for eac h v ertex i = 1 ;:::;n; color v ertex i with a set of colorsas follo ws: 8 > < > : 1+ f k ( i 1) ;k ( i 1)+1 ;:::;ik 1 g (mod(2 k +1)) if i 2 k +1 1to k if i> 2 k +1and ev en k +1to 2 k if i> 2 k +1and odd F or example,to 4-color C 15 withninecolors, w ew ouldfollo wthe abo v eprocedureto produce theresultillustratedinFigure2. W eha v esho wn that k ( G )= l 2 nk n 1 m for k< n 2 No w if k> n 2 ,then: k ( C n ) n 1 2 ( C n )+ k ( n 1 2 ) ( C n )= & 2 n ( n 1 2 ) n 1 + & 2 n ( k ( n 1 2 ) n 1 = & 2 nk n 1 : Therefore, k ( C n )= l 2 nk n 1 m for n odd. 2 2.2 Mycielskians of Cycles W eno w pro v eresultsregarding thec hromaticstabilit yofMycieskiansof cycles. 8

PAGE 16

v 5678 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v 1239 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v 4567 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v 1289 pp ppp pppp ppp ppp ppp ppp pppp ppp ppp ppp ppp pppp ppp ppp ppp pppp ppp ppp ppp ppp pppp ppp ppp ppp ppp p v 3456 p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p pp p p p p p p p p p p p p p p pp p p p p v 1789 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v 2345 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v 6789 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v 1234 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v 5678 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v 1234 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v 5678 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v 1234 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v 5678 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v 1234 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p Figure2: A4-coloring of C 15 withninecolors. 9

PAGE 17

2.2.1 Mycielskians of Ev en Cycles As with ev en cycles, the Mycielskians of ev en cycles ha v e the propert y of c hromaticstabilit y Theorem 2.3. F or n even, k ( ( G ))= l 5 k 2 m : Proof: Eac h ( C n ), n ev en, con tains an induced 5-cycle. By Theorem 2.2, a minim um k -coloringofa5-cyclerequires l 5 k 2 m colors,therefore k ( ( C n )) l 5 k 2 m T osho w k ( ( C n )) l 5 k 2 m ,w euseaproofb yinduction. F or n ev en, ( C n ) f z g is a bipartite graph, and hence,ma ybe 1-colored with t w o colors. Coloring the cen terwithathirdcolorsho wsthat 1 ( ( C n )) l 5 2 m Additionally ( C n ) f z g ma y be 2-colored with four colors b y coloring one partite set with the colors 1 and2,andtheotherwithcolors3and4. No wreplace1and3ontheinnernodes b y5. Thenthecen terma ybecoloredb y1and3. Therefore, 2 ( ( C n )) l 5(2) 2 m F or k> 2,assume k 2 ( ( C n )) l 5( k 2) 2 m : Then k ( ( C n )) k 2 ( ( C n ))+ 2 ( ( C n )) & 5( k 2) 2 +5= & 5 k 2 : Therefore,theMycielskianofan ev encycleisc hromaticallystable. 2 2.2.2 Mycielskians of Odd Cycles Stahl [ 6 ] sho w ed that ( C n ) is c hromatically unstable when n = 5. W e will sho w the samepropert yholds when n =7 ; 9 ; 11 ; and 13. Of specialimportance is the fact that the c hromatic stabilit y n um ber rises to three for ( C 11 ). F or 10

PAGE 18

completeness,w ebeginb ysho wing that ( C 3 )isc hromaticallystable. Theorem 2.4. k ( ( C 3 ))= l 10 k 3 m for k =1,2,3, ::: Proof: Since f ( C 3 )=3 and f ( ( G ))= f ( G )+ 1 f ( G ) w eha v e f ( ( C 3 ))= 10 3 Then k ( ( C 3 )) d k f ( C 3 ) e = l 10 k 3 m : T o sho w k ( ( C 3 )) l 10 k 3 m w e rst illustrate that the inequalit y holds for k =1 ; 2 ; and 3 b ysho wingtheappropriate k -colorings inFigure3. s a s b s c s c s a s b s d ( ( ( ( ( ( ( (h h h h h h h h @ @ @ @ @ L L L L L L J J J J J J J J J J J n n n n n n n n n n n H H H s ab s cd s ef s eg s ag s cg s bd ( ( ( ( ( ( ( ( h h h h h h h h @ @ @ @ @ L L L L L L J J J J J J J J J J J n n n n n n n n n n n H H H s abc s def s ghi s ghj s abj s dej s cfi ( ( ( ( ( ( ( (h h h h h h h h @ @ @ @ @ L L L L L L J J J J J J J J J J J n n n n n n n n n n n H H H Figure3: 1-, 2-,and 3-colorings of ( C 3 ). Usinginduction,for k> 3,assume k 3 ( ( C 3 )) l 10( k 3) 3 m Then k ( ( C 3 )) k 3 ( ( C 3 ))+ 3 ( ( C 3 )) & 10( k 3) 3 +10= & 10 k 3 : Therefore, k ( ( C 3 ))= l 10 k 3 m for k> 1. 2 11

PAGE 19

W eno wpresen texamplesofgraphs whic harec hromaticallyunstable,beginningwitha proof of Stahl'sresultfor ( C 5 ). W ewillusethefollo winglemm a. Lemma2.2. 1 ( ( C n ))=4 for n o dd. Proof: Sincethec hromaticn um berofan yoddcycleis3,theresultfollo wsfrom (9). 2 Theorem 2.5. k ( ( C 5 ))= ( 4 for k =1 l 29 k 10 m otherwise Proof: Since f ( C 5 )= 5 2 and f ( ( G ))= f ( G )+ 1 f ( G ) ,w e ha v e f ( ( C 5 ))= 29 10 Then k ( ( C 5 )) d k f ( C 5 ) e = l 29 k 10 m : This lo w erbound holds for all k> 1. Ho w ev er,for k =1,Lemma2.2 sho ws 1 ( ( C 5 ))=4. W e no w ha v e only to sho w that k ( ( C 5 )) l 29 k 10 m for k > 1. This is done with a proof b yinduction. F or k =2, 3, 10, and 11, T able 1 illustratesthat the inequalit yholds. F urthermore,since k + l ( G ) k ( G )+ l ( G ): 4 ( ( C 5 )) 2 ( ( C 5 )) + 2 ( ( C 5 )) = 12 5 ( ( C 5 )) 2 ( ( C 5 )) + 3 ( ( C 5 )) = 15 6 ( ( C 5 )) 3 ( ( C 7 )) + 3 ( ( C 5 )) = 18 7 ( ( C 5 )) 3 ( ( C 5 )) + 4 ( ( C 5 )) = 21 8 ( ( C 5 )) 4 ( ( C 5 )) + 4 ( ( C 5 )) = 24 9 ( ( C 5 )) 4 ( ( C 5 )) + 5 ( ( C 5 )) = 27 Th us, k ( ( C 5 )) l 29 k 10 m for 2 k 11. F or k > 11, assume k 10 ( ( C 5 )) l 29( k 10) 10 m Then k ( ( C 5 )) k 10 ( ( C 5 ))+ 10 ( ( C 5 )) & 29( k 10) 10 +29= & 29 k 10 : 12

PAGE 20

maximal k independen tsets 2 3 10 11 f x 1 ;x 3 ;y 1 ;y 3 g 1 1 3 3 f x 2 ;x 4 ;y 2 ;y 4 g 0 1 3 3 f x 3 ;x 5 ;y 3 ;y 5 g 0 1 3 4 f x 4 ;x 1 ;y 4 ;y 1 g 1 1 3 3 f x 5 ;x 2 ;y 5 ;y 2 g 1 1 3 3 f x 1 ;x 3 ;z g 0 1 2 3 f x 2 ;x 4 ;z g 1 0 2 2 f x 3 ;x 5 ;z g 1 0 2 1 f x 4 ;x 1 ;z g 0 1 2 2 f x 5 ;x 2 ;z g 0 1 2 3 f x 4 ;y 1 ;y 2 ;y 4 g 0 0 0 1 f y 1 ;y 2 ;y 3 ;y 4 ;y 5 g 1 1 4 4 k ( ( C 5 )) 6 9 29 32 T able1: Thew eigh ton eac hindependen tsetinak-coloring of ( C 5 ). Therefore, k ( ( C 5 ))= l 29 k 10 m for k> 1. 2 Theorem 2.6. k ( ( C 7 ))= ( 4 for k =1 l 58 k 21 m otherwise Proof: Since f ( C 7 )= 7 3 ,and f ( ( G ))= f ( G )+ 1 f ( G ) ,w eha v e f ( ( C 7 ))= 58 21 Then k ( ( C 7 )) d k f ( ( C 7 )) e = l 58 k 21 m : This lo w er bound holds for all k> 1. Ho w ev er,for k =1, Lemma2.2sho ws that 1 ( ( C 7 ))=4. W e no w sho w that k ( ( C 7 )) l 58 k 21 m for k > 1. W e will perform a proof b y induction. F or k = 2, 3, 5, 6, 9, 13, 17, and 21, T able 2 illustrates that the inequalit yholds. F urthermore,since k + l ( G ) k ( G )+ l ( G ): 13

PAGE 21

maximal k independen tsets 2 3 5 6 9 13 17 21 f x 1 ;x 3 ;x 5 ;y 1 ;y 3 ;y 5 g 0 0 1 1 2 2 3 4 f x 2 ;x 4 ;x 6 ;y 2 ;y 4 ;y 6 g 0 0 1 1 1 2 3 4 f x 3 ;x 5 ;x 7 ;y 3 ;y 5 ;y 7 g 0 1 1 1 1 3 3 4 f x 4 ;x 6 ;x 1 ;y 4 ;y 6 ;y 1 g 0 1 1 1 2 4 4 4 f x 5 ;x 7 ;x 2 ;y 5 ;y 7 ;y 2 g 0 1 1 1 2 2 3 4 f x 6 ;x 1 ;x 3 ;y 6 ;y 1 ;y 3 g 1 0 1 1 2 2 3 4 f x 7 ;x 2 ;x 4 ;y 7 ;y 2 ;y 4 g 1 0 1 1 2 2 3 4 f x 1 ;x 3 ;x 5 ;z g 1 1 1 1 1 3 3 3 f x 2 ;x 4 ;x 6 ;z g 1 1 1 1 2 2 3 3 f x 3 ;x 5 ;x 7 ;z g 0 0 1 1 2 0 2 3 f x 4 ;x 6 ;x 1 ;z g 0 0 1 1 1 0 1 3 f x 5 ;x 7 ;x 2 ;z g 0 0 0 1 1 2 2 3 f x 6 ;x 1 ;x 3 ;z g 0 1 0 1 1 3 3 3 f x 7 ;x 2 ;x 4 ;z g 0 1 1 1 1 3 3 3 f x 5 ;x 7 ;y 2 ;y 3 ;y 5 ;y 7 g 1 0 0 0 0 1 1 0 f y 1 ;y 2 ;y 3 ;y 4 ;y 5 ;y 6 ;y 7 g 1 2 2 3 4 5 7 9 k ( ( C 7 )) 6 9 14 17 25 36 47 58 T able2: Thew eigh ton eac hindependen tsetinak-coloring of ( C 7 ). 14

PAGE 22

4 ( ( C 7 )) 2 ( ( C 7 )) + 2 ( ( C 7 )) = 12 7 ( ( C 7 )) 2 ( ( C 7 )) + 5 ( ( C 7 )) = 20 8 ( ( C 7 )) 2 ( ( C 7 )) + 6 ( ( C 7 )) = 23 10 ( ( C 7 )) 5 ( ( C 7 )) + 5 ( ( C 7 )) = 28 11 ( ( C 7 )) 5 ( ( C 7 )) + 6 ( ( C 7 )) = 31 12 ( ( C 7 )) 6 ( ( C 7 )) + 6 ( ( C 7 )) = 34 14 ( ( C 7 )) 5 ( ( C 7 )) + 9 ( ( C 7 )) = 39 15 ( ( C 7 )) 6 ( ( C 7 )) + 9 ( ( C 7 )) = 42 16 ( ( C 7 )) 7 ( ( C 7 )) + 9 ( ( C 7 )) = 45 18 ( ( C 7 )) 9 ( ( C 7 )) + 9 ( ( C 7 )) = 50 19 ( ( C 7 )) 9 ( ( C 7 )) + 10 ( ( C 7 )) = 53 20 ( ( C 7 )) 10 ( ( C 7 )) + 10 ( ( C 7 )) = 56 22 ( ( C 7 )) 9 ( ( C 7 )) + 13 ( ( C 7 )) = 61 Th us far, w e ha v e k ( ( C 7 )) l 58 k 21 m for 2 k 22. F or k > 22, assume k 21 ( ( C 7 )) l 58( k 21) 21 m Then k ( ( C 7 )) k 21 ( ( C 7 ))+ 21 ( ( C 7 )) & 58( k 21) 21 +58= & 58 k 21 : Therefore, k ( ( C 7 ))= l 58 k 21 m for k> 1. 2 Theorem 2.7. k ( ( C 9 ))= ( 4 for k =1 l 97 k 36 m otherwise Proof: In a fashion similarto the previous theorem, w e nd that k ( ( C 9 )) l 97 k 36 m Since f ( C 9 ) = 9 4 f ( ( C 9 )) = 97 36 Then k ( ( C 9 )) d k f ( ( C 9 )) e = l 97 k 36 m But 1 ( ( C 9 ))doesnotmeetitslo w erboundof3,sinceLemma2.2sho ws 1 ( ( C 9 ))=4. T o sho w k ( ( C 9 )) l 97 k 36 m for k > 1, w e performa proof b y induction. F or k =2,3,4,5,7, 10,23, and 36,T able3 illustratesthat theinequalit yholds. F urthermore,since k + l ( G ) k ( G )+ l ( G ),w eha v e: 15

PAGE 23

maximal k independen tsets 2 3 4 5 7 10 23 36 f x 1 ;x 3 ;x 5 ;x 7 ;y 1 ;y 3 ;y 5 ;y 7 g 1 0 1 1 1 2 3 5 f x 2 ;x 4 ;x 6 ;x 8 ;y 2 ;y 4 ;y 6 ;y 8 g 0 0 0 1 1 1 4 5 f x 3 ;x 5 ;x 7 ;x 9 ;y 3 ;y 5 ;y 7 ;y 9 g 0 0 0 1 1 1 3 5 f x 4 ;x 6 ;x 8 ;x 1 ;y 4 ;y 6 ;y 8 ;y 1 g 0 0 0 0 1 1 3 5 f x 5 ;x 7 ;x 9 ;x 2 ;y 5 ;y 7 ;y 9 ;y 2 g 0 1 0 0 1 1 3 5 f x 6 ;x 8 ;x 1 ;x 3 ;y 6 ;y 8 ;y 1 ;y 3 g 1 1 1 1 1 1 3 5 f x 7 ;x 9 ;x 2 ;x 4 ;y 7 ;y 9 ;y 2 ;y 4 g 1 1 1 1 1 1 3 5 f x 8 ;x 1 ;x 3 ;x 5 ;y 8 ;y 1 ;y 3 ;y 5 g 0 1 1 1 1 2 3 5 f x 9 ;x 2 ;x 4 ;x 6 ;y 9 ;y 2 ;y 4 ;y 6 g 0 1 1 1 1 2 3 5 f x 1 ;x 3 ;x 5 ;x 7 ;z g 0 2 0 1 1 0 2 4 f x 2 ;x 4 ;x 6 ;x 8 ;z g 0 1 1 1 1 1 1 4 f x 3 ;x 5 ;x 7 ;x 9 ;z g 0 0 1 0 1 2 2 4 f x 4 ;x 6 ;x 8 ;x 1 ;z g 0 0 1 0 1 2 3 4 f x 5 ;x 7 ;x 9 ;x 2 ;z g 0 0 1 1 1 2 3 4 f x 6 ;x 8 ;x 1 ;x 3 ;z g 0 0 0 1 1 2 3 4 f x 7 ;x 9 ;x 2 ;x 4 ;z g 0 0 0 0 0 1 3 4 f x 8 ;x 1 ;x 3 ;x 5 ;z g 1 0 0 0 0 0 3 4 f x 9 ;x 2 ;x 4 ;x 6 ;z g 1 0 0 1 1 0 3 4 f x 3 ;x 5 ;x 7 ;y 1 ;y 3 ;y 5 ;y 7 ;y 9 g 0 0 0 0 0 0 1 0 f x 2 ;x 4 ;y 2 ;y 4 ;y 6 ;y 7 ;y 8 ;y 9 g 0 0 0 0 0 1 0 0 f y 1 ;y 2 ;y 3 ;y 4 ;y 5 ;y 6 ;y 7 ;y 8 ;y 9 g 1 1 2 2 3 4 10 16 k ( ( C 9 )) 6 9 11 14 19 27 62 97 T able3: Thew eigh ton eac hindependen tsetinak-coloring of ( C 9 ). 16

PAGE 24

F or k =6,8,9, and11: k ( ( C 9 )) 4 ( ( C 9 ))+ k 4 ( ( C 9 )) 11+ & 97( k 4) 36 = & 97 k 36 : F or k =12, 13, ::: ,22,24, 25, ::: ,35,and 37: k ( ( C 9 )) 10 ( ( C 9 ))+ k 10 ( ( C 9 )) 27+ & 97( k 10) 36 = & 97 k 36 : Th us far, w e ha v e k ( ( C 9 )) l 97 36 m for 2 k 37. F or k > 37, assume k 36 ( ( C 9 )) l 97( k 36) 36 m Then k ( ( C 9 )) k 36 ( ( C 9 ))+ 36 ( ( C 9 )) & 97( k 36) 36 +97= & 97 k 36 : Therefore, k ( ( C 9 )) l 97 36 m forall k> 37,and theproof iscomplete. 2 W econ tin uetoproofsofthec hromaticinstabilit yof ( C 11 )and ( C 13 ). Note that thec hromaticstabilit yn um berhas increasedfrom1 to3. Lemma2.3. 3 ( ( C 11 ))=9 : Proof: W e rst sho w that 3 ( ( C 11 )) 9. Suppose not. Then w e are able to nd eigh tindependen tsets of ( C 11 )suc h that eac hnode isincludedinat least three sets. T o color all t w en t y-three nodes with three colors eac h, w e need at least23 3=69 node-colors total. Label the nodes as before, with the outer nodes labeled x 1 through x 11 the innernodes y 1 through y 11 ,and thecen ter z Thelargestindependen tsetwhic h includes z isthe t ypeof set sho wn in Figure4. W ereferto this t ypeof set as a 17

PAGE 25

v X v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp p v v pp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X vp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p Figure4: Oneof 11 T ype Z independen tsets of ( C 11 ). 18

PAGE 26

T ype Z independen tset and noticethat through rotation, thereare elev ensuc h sets. Three T ype Z independen t sets are requiredto 3-color z pro viding at most 3 6=18 node-colors. W e no w requireat mostv eadditional independen tsets whic htogetherpro videat least51 node-colors. Theuniquelargestindependen tsetof ( C 11 )istheoneconsistingoftheelev en innernodes. Callthisseta T ype Y set,illustratedinFigure5. v v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp p v v X pp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p Figure5: T ype Y independen tsetof ( C 11 ). A t least one T ype Y set m ust be used to pro vide 51 node-colors using v e 19

PAGE 27

independen t sets. Ho w ev er, if more than one T ype Y set is used, there are three or few er independen t sets with whic h to color the outer nodes. Since an y independen t set con tains at mostv e outer nodes, these three independen t sets com binedwiththethreeindependen tsetsofT ype Z pro videatmost3 5+3 5 = 30 node-colors on the outer nodes. But since the outer nodes require at least 3 11=33node-colors,w em ustuseexactlyoneoftheT ype Y independen tsets. W e ha v e used four independen t sets, pro viding at most 18+11 = 29 nodecolors. So w e m ust nd four more independen t sets whic h together pro vide at least 40 node-colors. Sincew e can no longer use a T ype Y set, the only t ype of independen tsetcon tainingelev ennodes,eac hofthefourindependen tsetsm ust con tain ten nodes, for a total of exactly 69 node-colors. In other w ords, eac h node m ustbeincludedinexactlythreeindependen tsets. Eac h T ype Z independen t set pro vides v e node-colors on the outer nodes. Therefore, w e need exactly 33 (3 5) = 18 more node-colors on the outer nodes. There are t w o cases whic h satisfy this criteria. See Figures 6 through 8 for illustrationsof thefollo wingt ypesofindependen tsets. Case 1: Three T ype X 5 one T ype X 3 Oneindependen tsetofT ype X 3 colors sev en inner nodes. These nodes ha v e been previously colored b y an independen tset of T ype Y so eac h requiresinclusioninexactlyone more independen tset,asetofT ype X 5 Considerthefoursequen tialinnernodes 20

PAGE 28

oftheT ype X 3 set. W erequiret w odistinctindependen tsetsofT ype X 5 to completethe3-coloringofthesefournodes. Butthenthelastindependen t setofT ype X 5 cannotbeusedwithoutaddinganothercolortoatleastone of the four sequen tial inner nodes, an impossibilit y since eac h m ust ha v e exactlythreecolors. v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp p v v pp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p Figure6: Oneof 11 T ype X 5 independen tsetsof ( C 11 ). Case 2: Tw o T ype X 5 t w o T ype X 4 An yc hoiceofthet w oindependen tsets of T ype X 4 forces at least one inner node to be colored b y both of these 21

PAGE 29

v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp p v v pp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p Figure7: Oneof 11 T ype X 3 independen tsetsof ( C 11 ). 22

PAGE 30

v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp p v v pp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp pp ppp pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp ppp pp pp ppp pp ppp pp pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p pp p p p p pp p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v v p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p v X v X p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p Figure8: Oneof 11 T ype X 4 independen tsetsof ( C 11 ). 23

PAGE 31

independen tsets. Callthis node y j Since y j w as already 1-colored b ythe independen t set of T ype Y it is no w 3-colored. Therefore, w e cannot include y j ineitherof thet w oT ype X 5 sets tobe used. Then x j willnot be includedinaT ype X 5 seteither,andthereforem ustha v ebeencoloredb y threeindependen tsetsofT ype Z Consider x j +1 ,whic hisadjacen ttoboth x j and y j Since x j and y j arecolored b ysixdistinctindependen tsets,w e w ouldrequirethreemoredistinctindependen tsetstocolor x j +1 ,foratotal ofnine,acon tradictionofourh ypothesisthat ( C 11 )canbe3-coloredwith eigh tcolors. W e ha v e sho wn that 3 ( ( C 11 )) 9 : T able 4 illustrates that ( C 11 ) can be 3coloredwith9 colors;therefore, 3 ( ( C 11 )) 9. 2 Theorem 2.8. k ( ( C 11 ))= 8 > > < > > : 4 for k =1 9 for k =3 l 146 k 55 m otherwise Proof: Similarto previoustheorems, f ( C 11 )= 11 5 ,whic himplies f ( ( C 11 ))= 146 55 ,and k ( ( C 11 )) l 146 k 55 m Butfor k =1 and 3, thislo w erbound isnot met, sinceLemma2.2sho ws 1 ( ( C 11 ))=4and Lemma2.3 sho ws 3 ( ( C 11 ))=9 : T o sho w k ( ( C 11 )) l 146 k 55 m for k = 2, 4, 5, 6, ::: w e perform a proof b y induction. F or k = 2, 4, 5, 6, 7, 9, 29, 32, and 55, T able 4 illustrates that the inequalit yholds. F or k = 8, 10, 11, ::: 28, 30, 31, 33, 34, ::: 54, 56, and 57, w eha v e k ( ( C 11 )) 6 ( ( C 11 ))+ k 6 ( ( C 11 ))= l 146 k 55 m : F or k =58, w e ha v e 24

PAGE 32

58 ( ( C 11 )) 29 ( ( C 11 ))+ 29 ( ( C 11 ))= l 146(58) 55 m : Th us far, w e ha v e k ( ( C 11 )) l 146 k 55 m for k = 2 ; 4 ; 5 ;:::; 58. F or k > 58, assume k 55 ( ( C 11 )) l 146( k 55) 55 m Then k ( ( C 11 )) k 55 ( ( C 11 ))+ 55 ( ( C 11 ))= l 146 k 55 m for k> 58, and w earedone. 2 Theorem 2.9. k ( ( C 13 ))= 8 > > < > > : 4 for k =1 8 or9 for k =3 l 205 k 78 m otherwise Proof: Since f ( C 13 )= 13 6 w eha v e f ( ( C 13 ))= 205 78 and k ( ( C 13 )) l 205 k 78 m : Lemma 2.2 sho ws 1 ( ( C 13 )) = 4. Computational results ha v e sho wn that 3 ( ( C 13 ) = 9. Ho w ev er, at the time of this paper, a theoretical proof does not exist. T able5 sho ws 3 ( ( C 13 )) 9 : W epro v e k ( ( C 13 )) l 205 k 78 m for k =2,4,5,6, ::: b yinduction. F or k =2,4, 5,6,7,9,11,14,19,27,35,and78,T able5illustratesthattheinequalit yholds. F or k =8,10,and12,w eha v e k ( ( C 13 )) 6 ( ( C 13 ))+ k 6 ( ( C 13 ))= l 205 k 78 m : F or k = 54, 62, and 70, w e ha v e k ( ( C 13 )) 35 ( ( C 13 ))+ k 35 ( ( C 13 )) = l 205 k 78 m : F or k = 13 through 81 except 14, 19, 27, 35, 54, 62, and 70, w e ha v e k ( ( C 13 )) 11 ( ( C 13 ))+ k 11 ( ( C 13 ))= l 205 k 78 m : F or k> 81,assume k 78 ( ( C 13 )) l 205( k 78) 78 m Then k ( ( C 13 )) k 78 ( ( C 13 ))+ 78 ( ( C 13 ))= l 205 k 78 m for k> 81, and w earedone. 2 25

PAGE 33

maximal k independen t sets 2 3 4 5 6 7 9 29 32 55 f x 1 ;x 3 ;x 5 ;x 7 ;x 9 ;y 1 ;y 3 ;y 5 ;y 7 ;y 9 g 0 0 0 1 0 1 1 3 3 6 f x 2 ;x 4 ;x 6 ;x 8 ;x 10 ;y 2 ;y 4 ;y 6 ;y 8 ;y 10 g 1 0 1 1 1 1 1 3 3 6 f x 3 ;x 5 ;x 7 ;x 9 ;x 11 ;y 3 ;y 5 ;y 7 ;y 9 ;y 11 g 0 0 1 1 0 1 1 4 3 6 f x 4 ;x 6 ;x 8 ;x 10 ;x 1 ;y 4 ;y 6 ;y 8 ;y 10 ;y 1 g 0 1 1 1 0 0 1 3 3 6 f x 5 ;x 7 ;x 9 ;x 11 ;x 2 ;y 5 ;y 7 ;y 9 ;y 11 ;y 2 g 0 1 0 1 1 0 1 3 3 6 f x 6 ;x 8 ;x 10 ;x 1 ;x 3 ;y 6 ;y 8 ;y 10 ;y 1 ;y 3 g 0 0 0 0 0 1 1 3 3 6 f x 7 ;x 9 ;x 11 ;x 2 ;x 4 ;y 7 ;y 9 ;y 11 ;y 2 ;y 4 g 1 0 0 0 0 1 1 3 3 6 f x 8 ;x 10 ;x 1 ;x 3 ;x 5 ;y 8 ;y 10 ;y 1 ;y 3 ;y 5 g 0 1 0 0 1 1 1 3 3 6 f x 9 ;x 11 ;x 2 ;x 4 ;x 6 ;y 9 ;y 11 ;y 2 ;y 4 ;y 6 g 0 1 1 0 1 0 1 3 4 6 f x 10 ;x 1 ;x 3 ;x 5 ;x 7 ;y 10 ;y 1 ;y 3 ;y 5 ;y 7 g 1 1 1 1 1 1 1 3 3 6 f x 11 ;x 2 ;x 4 ;x 6 ;x 8 ;y 11 ;y 2 ;y 4 ;y 6 ;y 8 g 0 0 0 1 0 1 1 3 5 6 f x 1 ;x 3 ;x 5 ;x 7 ;x 9 ;z g 1 0 1 1 1 0 1 3 2 5 f x 2 ;x 4 ;x 6 ;x 8 ;x 10 ;z g 0 0 0 1 0 1 1 2 4 5 f x 3 ;x 5 ;x 7 ;x 9 ;x 11 ;z g 0 1 0 1 1 1 1 1 4 5 f x 4 ;x 6 ;x 8 ;x 10 ;x 1 ;z g 0 0 0 1 1 1 1 2 4 5 f x 5 ;x 7 ;x 9 ;x 11 ;x 2 ;z g 0 0 0 1 0 1 1 3 4 5 f x 6 ;x 8 ;x 10 ;x 1 ;x 3 ;z g 0 1 0 0 1 0 0 3 4 5 f x 7 ;x 9 ;x 11 ;x 2 ;x 4 ;z g 0 1 1 0 1 1 0 3 4 5 f x 8 ;x 10 ;x 1 ;x 3 ;x 5 ;z g 0 0 1 0 0 1 1 3 3 5 f x 9 ;x 11 ;x 2 ;x 4 ;x 6 ;z g 0 0 0 0 0 0 1 3 2 5 f x 10 ;x 1 ;x 3 ;x 5 ;x 7 ;z g 0 0 0 0 0 0 1 3 1 5 f x 11 ;x 2 ;x 4 ;x 6 ;x 8 ;z g 1 0 1 0 1 0 1 3 0 5 f x 1 ;x 3 ;x 5 ;x 7 ;y 1 ;y 3 ;y 5 ;y 7 ;y 9 ;y 10 g 0 0 0 0 0 0 0 0 2 0 f x 1 ;x 3 ;x 5 ;x 10 ;y 1 ;y 3 ;y 5 ;y 7 ;y 8 ;y 10 g 0 0 0 0 0 0 0 0 1 0 f x 1 ;x 6 ;x 8 ;x 10 ;y 1 ;y 3 ;y 4 ;y 6 ;y 8 ;y 10 g 0 0 0 0 1 0 0 0 0 0 f x 2 ;x 4 ;x 6 ;x 11 ;y 2 ;y 4 ;y 6 ;y 8 ;y 9 ;y 11 g 0 0 0 0 0 1 0 0 0 0 f x 3 ;x 5 ;x 7 ;x 9 ;y 1 ;y 3 ;y 5 ;y 7 ;y 9 ;y 11 g 0 0 0 0 1 0 0 0 0 0 f x 4 ;x 6 ;x 8 ;x 10 ;y 1 ;y 2 ;y 4 ;y 6 ;y 8 ;y 10 g 0 0 0 0 0 0 0 1 0 0 f x 1 ;x 3 ;x 6 ;x 9 ;z g 0 0 0 0 0 1 0 0 0 0 f x 2 ;x 4 ;x 11 ;y 2 ;y 4 ;y 6 ;y 7 ;y 8 ;y 9 ;y 11 g 0 0 0 0 1 0 0 0 0 0 f y 1 ;y 2 ;y 3 ;y 4 ;y 5 ;y 6 ;y 7 ;y 8 ;y 9 ;y 10 ;y 11 g 1 1 2 2 2 3 4 13 14 25 k ( ( C 11 )) 6 9 11 14 16 19 24 77 85 146 T able4: The w eigh ton eac hindependen tsetina k-coloringof ( C 11 ). 26

PAGE 34

maximal k independen tsets 2 3 4 5 6 7 9 11 14 19 27 35 78 f x 1 ;x 3 ;x 5 ;x 7 ;x 9 ;x 11 ;y 1 ;y 3 ;y 5 ;y 7 ;y 9 ;y 11 g 1 1 0 0 0 0 1 1 1 1 3 3 7 f x 2 ;x 4 ;x 6 ;x 8 ;x 10 ;x 12 ;y 2 ;y 4 ;y 6 ;y 8 ;y 10 ;y 12 g 1 1 0 0 0 0 1 1 2 1 3 3 7 f x 3 ;x 5 ;x 7 ;x 9 ;x 11 ;x 13 ;y 3 ;y 5 ;y 7 ;y 9 ;y 11 ;y 13 g 1 1 0 0 0 0 1 1 0 1 3 3 7 f x 4 ;x 6 ;x 8 ;x 10 ;x 12 ;x 1 ;y 4 ;y 6 ;y 8 ;y 10 ;y 12 ;y 1 g 0 1 0 0 0 1 1 1 1 2 2 3 7 f x 5 ;x 7 ;x 9 ;x 11 ;x 13 ;x 2 ;y 5 ;y 7 ;y 9 ;y 11 ;y 13 ;y 2 g 0 0 0 1 1 1 1 1 1 2 2 4 7 f x 6 ;x 8 ;x 10 ;x 12 ;x 1 ;x 3 ;y 6 ;y 8 ;y 10 ;y 12 ;y 1 ;y 3 g 0 0 0 1 1 1 1 1 0 2 2 3 7 f x 7 ;x 9 ;x 11 ;x 13 ;x 2 ;x 4 ;y 7 ;y 9 ;y 11 ;y 13 ;y 2 ;y 4 g 0 0 0 1 1 1 1 1 0 2 2 3 7 f x 8 ;x 10 ;x 12 ;x 1 ;x 3 ;x 5 ;y 8 ;y 10 ;y 12 ;y 1 ;y 3 ;y 5 g 0 0 1 1 1 1 1 1 0 2 2 3 7 f x 9 ;x 11 ;x 13 ;x 2 ;x 4 ;x 6 ;y 9 ;y 11 ;y 13 ;y 2 ;y 4 ;y 6 g 0 0 1 1 1 1 1 0 2 2 2 3 7 f x 10 ;x 12 ;x 1 ;x 3 ;x 5 ;x 7 ;y 10 ;y 12 ;y 1 ;y 3 ;y 5 ;y 7 g 0 0 1 1 1 1 1 1 1 2 2 3 7 f x 11 ;x 13 ;x 2 ;x 4 ;x 6 ;x 8 ;y 11 ;y 13 ;y 2 ;y 4 ;y 6 ;y 8 g 0 0 1 0 1 1 0 1 2 1 2 3 7 f x 12 ;x 1 ;x 3 ;x 5 ;x 7 ;x 9 ;y 12 ;y 1 ;y 3 ;y 5 ;y 7 ;y 9 g 0 0 1 0 0 1 0 1 1 1 2 3 7 f x 13 ;x 2 ;x 4 ;x 6 ;x 8 ;x 10 ;y 13 ;y 2 ;y 4 ;y 6 ;y 8 ;y 10 g 0 1 0 0 0 0 1 0 1 1 3 3 7 f x 1 ;x 3 ;x 5 ;x 7 ;x 9 ;x 11 ;z g 0 0 1 1 1 1 1 1 1 3 1 3 6 f x 2 ;x 4 ;x 6 ;x 8 ;x 10 ;x 12 ;z g 0 0 1 1 1 1 1 1 0 3 0 3 6 f x 3 ;x 5 ;x 7 ;x 9 ;x 11 ;x 13 ;z g 0 0 1 1 1 1 1 0 1 2 0 3 6 f x 4 ;x 6 ;x 8 ;x 10 ;x 12 ;x 1 ;z g 1 0 0 1 1 1 1 0 0 0 2 2 6 f x 5 ;x 7 ;x 9 ;x 11 ;x 13 ;x 2 ;z g 0 1 0 0 0 0 1 1 0 0 3 1 6 f x 6 ;x 8 ;x 10 ;x 12 ;x 1 ;x 3 ;z g 0 0 0 0 0 0 0 1 3 1 3 2 6 f x 7 ;x 9 ;x 11 ;x 13 ;x 2 ;x 4 ;z g 0 0 0 0 0 0 0 1 4 1 3 3 6 f x 8 ;x 10 ;x 12 ;x 1 ;x 3 ;x 5 ;z g 0 0 0 0 0 0 1 1 2 1 3 3 6 f x 9 ;x 11 ;x 13 ;x 2 ;x 4 ;x 6 ;z g 0 0 0 0 0 1 0 1 0 0 3 3 6 f x 10 ;x 12 ;x 1 ;x 3 ;x 5 ;x 7 ;z g 0 0 0 0 0 0 0 1 0 0 3 3 6 f x 11 ;x 13 ;x 2 ;x 4 ;x 6 ;x 8 ;z g 0 0 0 0 0 0 1 1 0 2 3 3 6 f x 12 ;x 1 ;x 3 ;x 5 ;x 7 ;x 9 ;z g 0 2 0 0 1 1 1 1 1 3 2 3 6 f x 13 ;x 2 ;x 4 ;x 6 ;x 8 ;x 10 ;z g 1 0 1 1 1 1 1 1 2 3 1 3 6 f x 1 ;x 3 ;x 5 ;x 12 ;y 1 ;y 3 ;y 5 ;y 7 ;y 8 ;y 9 ;y 10 ;y 12 g 0 0 0 0 0 0 0 0 1 0 0 0 0 f x 2 ;x 4 ;x 6 ;x 13 ;y 2 ;y 4 ;y 6 ;y 8 ;y 9 ;y 10 ;y 11 ;y 13 g 0 0 0 0 0 0 0 1 0 0 0 0 0 f x 3 ;x 5 ;x 7 ;x 9 ;y 1 ;y 3 ;y 5 ;y 7 ;y 9 ;y 11 ;y 12 ;y 13 g 0 0 0 0 0 0 0 0 0 0 1 0 0 f x 4 ;x 6 ;x 8 ;x 10 ;y 1 ;y 2 ;y 4 ;y 6 ;y 8 ;y 10 ;y 12 ;y 13 g 0 0 0 0 0 0 0 1 0 0 0 0 0 f x 5 ;x 7 ;x 9 ;x 11 ;y 1 ;y 2 ;y 3 ;y 5 ;y 7 ;y 9 ;y 11 ;y 13 g 0 0 0 0 0 0 0 0 1 0 0 0 0 f x 1 ;x 6 ;x 8 ;x 10 ;x 12 ;y 1 ;y 3 ;y 4 ;y 6 ;y 8 ;y 10 ;y 12 g 0 0 0 0 0 0 0 0 1 0 0 1 0 f x 2 ;x 4 ;x 6 ;x 11 ;x 13 ;y 2 ;y 4 ;y 6 ;y 8 ;y 9 ;y 11 ;y 13 g 0 0 0 0 0 0 0 0 0 1 0 0 0 f x 4 ;x 6 ;x 8 ;x 10 ;x 12 ;y 1 ;y 2 ;y 4 ;y 6 ;y 8 ;y 10 ;y 12 g 0 0 0 0 0 0 0 0 0 0 1 0 0 f x 5 ;x 7 ;x 9 ;x 11 ;x 13 ;y 2 ;y 3 ;y 5 ;y 7 ;y 9 ;y 11 ;y 13 g 0 0 0 0 0 0 0 0 1 1 0 0 0 f x 1 ;x 10 ;x 12 ;y 1 ;y 3 ;y 4 ;y 5 ;y 6 ;y 7 ;y 8 ;y 10 ;y 12 g 0 0 0 0 0 0 0 0 1 1 0 0 0 f x 3 ;x 5 ;x 7 ;y 1 ;y 3 ;y 5 ;y 7 ;y 9 ;y 10 ;y 11 ;y 12 ;y 13 g 0 0 0 0 0 0 0 0 1 0 0 0 0 f x 9 ;x 11 ;x 13 ;y 2 ;y 3 ;y 4 ;y 5 ;y 6 ;y 7 ;y 9 ;y 11 ;y 13 g 0 0 0 0 0 0 0 1 0 0 0 0 0 f x 3 ;x 5 ;y 1 ;y 3 ;y 5 ;y 7 ;y 8 ;y 9 ;y 10 ;y 11 ;y 12 ;y 13 g 0 0 0 0 0 0 0 0 1 0 0 0 0 f y 1 through y 13 g 1 1 2 3 3 3 4 4 4 8 12 16 36 k ( ( C 13 )) 6 9 11 14 16 19 24 29 37 50 71 92 205 T able5: The w eigh ton eac hindependen tsetina k-coloringof ( C 13 ). 27

PAGE 35

3 Instabilit y in Multiclique Sequences Mycielskiansofoddcyclesha v epro videdin terestingresultsinc hromaticinstabilit y Thesegraphs also pro v etobeusefulindisco v eringinstabilit yinm ulticli que sequences. 3.1 Cycles W erst sho wthat allcyclesarecliquishlystable. Theorem 3.1. F or n even, k ( C n )=2 k Proof: The k -clique n um ber of a graph is the maxim um total in teger w eigh t whic h can be placed on the nodes so that eac h independen t set has w eigh t at most k An ev en cycle is a bipartite graph; therefore, since w e cannot put a w eigh t of more than k on either partite set, k 2 k But b y placing a total w eigh t of k on the nodes of eac h partite set, w e nd a k -clique, so k 2 k Therefore,ev eryev encycleiscliquishlystable. 2 Theorem 3.2. F or n o dd, k ( C n )= j 2 nk n 1 k Proof: Since f ( C n ) = f ( C n ) = 2 n n 1 for n odd, and k b k! f c w e ha v e k j 2 nk n 1 k T o sho w thecon v erse,note that 2 k = j 2 nk n 1 k when k < n 2 If k < n 2 thena k -cliqueofv alue2 k ma ybeformedb yplacingaw eigh tof k oneac hoft w o 28

PAGE 36

adjacen t nodes in the cycle. Therefore, for k < n 2 ;! k ( G ) j 2 nk n 1 k So if k > n 2 then: k ( C n ) n 1 2 ( C n )+ k ( n 1 2 ) ( C n )= $ 2 n ( n 1 2 ) n 1 % + $ 2 n ( k ( n 1 2 ) n 1 % = $ 2 nk n 1 % : Therefore,allodd cyclesarecliquishlystable. 2 3.2 Mycielskians of Cycles W e no w proceed to results regarding the cliquish stabilit y of Mycielskians of cycles. 3.2.1 Mycielskians of Ev en Cycles. W esho w that Mycielskiansofev encyclesare cliquishlyunstable. Theorem 3.3. F or n even, ( C n )= j 5 k 2 k Proof: F or n ev en, ( C n ) con tains an induced 5-cycle. Since k ( C 5 ) = j 5 k 2 k w e ha v e k ( ( C n )) j 5 k 2 k W esho w that k ( ( C n )) j 5 k 2 k through a proof b y induction. F or n ev en,w ema ynda1-cliqueof ( C n )withv alue2b yassigning aw eigh tof1toeac hoft w oadjacen touternodes. Additionally ,w ema ynda2cliqueofv alue5b yassigningaw eigh tof1toeac hofthefollo wing: t w oadjacen t outernodes,sa y x i and x i +1 ,thecorrespondinginnernodes, y i and y i +1 ,andthe cen ternode z Therefore,when k =1or2,w eha v e k ( ( C n )) j 5 k 2 k F or k> 2, assume k 2 ( ( C n )) j 5( k 2) 2 k Then k ( ( C n )) k 2 ( ( C n ))+ 2 ( ( C n )) $ 5( k 1) 2 % +5= $ 5 k 2 % : 29

PAGE 37

Therefore,Mycielskiansofev encyclesare cliquishlystable. 2 3.2.2 Mycielskians of Odd Cycles W e begin b y sho wing that for n = 3 and 5, w e ha v e that ( C n ) is stable in its m ulticli quesequence. In the follo wing proofs, w e let a i ;b i ; and c represen t the w eigh tsonnodes x i ;y i ; and z respectiv ely Inaddition,let a = a 1 + a 2 + + a n and b = b 1 + b 2 + + b n Theorem 3.4. k ( ( C 3 ))= j 10 k 3 k Proof: Since f ( ( C 3 ))= f ( ( C 3 ))= 10 3 ,w eha v e k ( ( C 3 )) b k f ( ( C 3 )) c = j 10 k 3 k W e sho w that k ( ( C 3 )) j 10 k 3 k for k = 1 ; 2 ; and 3 b y presen ting the appropriate k-cliquesinFigure9. F or k> 3 assume k 3 ( ( C 3 )) j 10( k 3) 3 k Then b yinduction, k ( ( C 3 )) k 3 ( ( C 3 ))+ 3 ( ( C 3 )) $ 10( k 3) 3 % +10= $ 10 k 3 % ; whic hconcludesour proof. 2 Lemma3.1. F or k =9+10 h wher e h 0 and inte ger, k ( ( C 5 )) j 29 k 10 k 1 : Proof: F or k = 9+10 h w e can algebraically sho w that j 29 k 10 k 1 = 25+29 h Therearet w ocases. Case 1: c 4+4 h: W eha v ev eindependen tsetsof ( C 5 )oftheform f x 1 ;x 3 ;z g f x 2 ;x 4 ;z g ::: f x 5 ;x 2 ;z g Since a 1 + a 3 + c 9+10 h a 2 + a 4 + c 9+10 h 30

PAGE 38

s 1 s 1 s 1 s 0 s 0 s 0 s 0 ( ( ( ( ( ( ( (h h h h h h h h @ @ @ @ @ L L L L L L J J J J J J J J J J J n n n n n n n n n n n H H H s 2 s 2 s 2 s 0 s 0 s 0 s 0 ( ( ( ( ( ( ( ( h h h h h h h h @ @ @ @ @ L L L L L L J J J J J J J J J J J n n n n n n n n n n n H H H s 2 s 2 s 2 s 1 s 1 s 1 s 1 ( ( ( ( ( ( ( (h h h h h h h h @ @ @ @ @ L L L L L L J J J J J J J J J J J n n n n n n n n n n n H H H Figure9: 1-,2-, and3-cliquesof ( C 3 ). 31

PAGE 39

::: a 5 + a 2 + c 9+10 h w eha v ethat a = a 1 + a 3 2 + a 2 + a 4 2 + a 3 + a 5 2 + a 4 + a 1 2 + a 5 + a 2 2 5 9+10 h c 2 : Additionally ,theindependen tset f y 1 ;y 2 ;y 3 ;y 4 ;y 5 g hasw eigh tatmost9+ 10 h Therefore,summingthew eigh tso v erallnodes: 9+10 h ( ( C 5 ))= a + b + c 45+50 h 5 2 +(9+10 h )+ c 25+29 h: Case 2: c 3+4 h: No w w e use independen t sets of the form f x 1 ;x 3 ;y 1 ;y 3 g f x 2 ;x 4 ;y 2 ;y 4 g ::: f x 5 ;x 2 ;y 5 ;y 2 g Since a 1 + a 3 + b 1 + b 3 9 +10 h a 2 + a 4 + b 2 + b 4 9+10 h ::: a 5 + a 2 + b 5 + b 2 9+10 h w eha v e 9+10 h ( ( C 5 ))= a + b + c = ( a 1 + b 1 )+( a 3 + b 3 ) 2 + ( a 2 + b 2 )+( a 4 + b 4 ) 2 + ( a 3 + b 3 )+( a 5 + b 5 ) 2 + ( a 4 + b 4 )+( a 1 + b 1 ) 2 + ( a 5 + b 5 )+( a 2 + b 2 ) 2 + c 5 9+10 h 2 + c 25+29 h: Therefore,for k =9+10 h w eha v e 9+10 h ( ( C 5 )) 25+29 h = j 29 k 10 k 1. 2 Theorem 3.5. k ( ( C 5 ))= 8 > > < > > : j 29 k 10 k 1 for k =9+10 h;h 0 and in teger j 29 k 10 k otherwise Proof: Since f ( ( C 5 ))= f ( ( C 5 ))= 29 10 ,then k ( ( C 5 )) b k! f ( G ) c = j 29 k 10 k ; for k =9+10 h Lemma3.1sho ws k ( ( C 5 )) j 29 k 10 k 1. T o pro v eequalit y ,w e useinduction. F or k 10,T able 6illustratesthatequalit yholds. 32

PAGE 40

k nodes 1 2 3 4 5 6 7 8 9 10 x 1 0 0 1 1 1 1 2 2 2 3 x 2 0 0 0 1 1 2 2 2 2 3 x 3 1 1 1 1 2 2 2 3 3 3 x 4 1 1 1 1 2 2 2 3 3 3 x 5 0 0 1 1 1 2 2 2 2 3 y 1 0 0 0 0 1 2 1 2 2 2 y 2 0 1 1 1 2 1 1 2 2 2 y 3 0 0 1 1 1 1 2 1 2 2 y 4 0 0 1 1 0 1 2 1 2 2 y 5 0 1 0 1 1 1 1 2 1 2 z 0 1 1 2 2 2 3 3 4 4 k ( ( C 5 )) 2 5 8 11 14 17 20 23 25 29 T able6: Thew eigh toneac hnode inak-cliqueof ( C 5 ). F or k > 10, assume that the result holds for k 10. Then since k ( ( C 5 )) k 10 ( ( C 5 ))+ 10 ( ( C 5 )),theresultfollo wsfor k> 10. 2 W eno w presen texamplesofgraphs whic harecliquishlyunstable. Lemma3.2. 3 ( ( C 7 )) 7 : Proof: Therearethreecases. Case 1: c 2 : Therearesev enindependen tsetsof ( C 7 )oftheform f x 1 ;x 3 ;x 5 ;z g f x 2 ;x 4 ;x 6 ;z g ::: f x 7 ;x 2 ;x 4 ;z g : Since a 1 + a 3 + a 5 + c 3, a 2 + a 4 + a 6 + c 3, ::: a 7 + a 2 + a 4 + c 3,w eha v e a = a 1 + a 3 + a 5 3 + a 2 + a 4 + a 6 3 + + a 7 + a 2 + a 4 3 7 3 c 3 : Theindependen tset f y 1 ;y 2 ;:::y 7 g hasw eigh tatmost3,therefore 3 ( ( C 7 )) = a + b + c 21 7 c 3 +3+ c 7 : 33

PAGE 41

Case 2: c = 0 : No w w e use independen t sets of the form f x 1 ;x 3 ;x 5 ;y 1 ;y 3 ;y 5 g f x 2 ;x 4 ;x 6 ;y 2 ;y 4 ;y 6 g ::: f x 7 ;x 2 ;x 4 ;y 7 ;y 2 ;y 4 g Since a 1 + a 3 + a 5 + b 1 + b 3 + b 5 3, a 2 + a 4 + a 6 + b 2 + b 4 + b 6 3, ::: a 7 + a 2 + a 4 + b 7 + b 2 + b 4 3, w eha v e 3 ( ( C 7 ))= a + b + c = ( a 1 + b 1 )+( a 3 + b 3 )+( a 5 + b 5 ) 3 + ( a 2 + b 2 )+( a 4 + b 4 )+( a 6 + b 6 ) 3 + + ( a 7 + b 7 )+( a 2 + b 2 )+( a 4 + b 4 ) 3 + c 7 : Case 3: c = 1 : Eac h independen t set of outer nodes f x 1 ;x 3 ;x 5 g f x 2 ;x 4 ;x 6 g ::: f x 7 ;x 2 ;x 4 g can ha v e a total w eigh t of at most 2, since including z in eac hsetformsa maximalindependen tset. So at leastone node of eac hof the abo v e sets has w eigh t0. Sinceeac h node is in threeof theabo v e sets, at leastthreeof theouternodes are w eigh ted0. W eha v et w ocases. Casea: Notwozer o-weighte douterno desar ese quential. Thentherem ust be exactly three zero-w eigh ted outer nodes. Without loss of generalit y suppose a 1 = a 3 = a 5 = 0. Since a i > 0 for i 6 = 1 ; 3 ; 5, it follo ws that a 7 + a 2 + a 4 + c 4. Butsince f x 7 ;x 2 ;x 4 ;z g isanindependen tset,w eha v e a 7 + a 2 + a 4 + c 3,acon tradiction. Case b: Two of the zer o-weighte d outer no des ar e se quential. Without loss of generalit y suppose the t w o sequen tial nodes are x 1 and x 2 34

PAGE 42

Thenallother nodes of ( C 7 ) arecon tainedin S = f x 3 ;x 5 ;x 7 ;y 3 ;y 5 ;y 7 g[ f x 4 ;x 6 ;y 1 ;y 2 ;y 4 ;y 6 g[f z g Butsince S is the union of t w o maximalindependen tsetsand z ,thetotalw eigh tonthenodesof S isatmost3+3+1=7. Therefore, 3 ( ( C 7 )) 7. 2 Lemma3.3. F or k = g +21 h wher e g =4 8 20 and h a nonne gative inte ger, k ( ( C 7 )) j 58 k 21 k 1 Proof: Let q g represen t an in teger associated with eac h g where q 4 = 2 ;q 8 = 4 ; and q 20 =9. F or k = g +21 h ,w ecansho w j 58 k 21 k 1= j 58 g 21 k +58 h 1. There aret w ocases. Case 1: c q g +9 h Since a 1 + a 3 + a 5 + c g +21 h a 2 + a 4 + a 6 + c g +21 h ::: a 7 + a 2 + a 4 + c g +21 h w eha v e a = a 1 + a 3 + a 5 3 + a 2 + a 4 + a 6 3 + + a 7 + a 2 + a 4 3 7 g +21 h c 3 : Additionally ,theindependen tset f y 1 ;y 2 ;:::;y 7 g hasw eigh tatmost g +21 h therefore: g +21 h ( ( C 7 ))= a + b + c 7 g +147 h 7 c 3 +( g +21 h )+ c 58 g 21 +58 h 1 : Case 2: c q g 1+9 h Since a 1 + a 3 + a 5 + b 1 + b 3 + b 5 g +21 h a 2 + a 4 + a 6 + b 2 + b 4 + b 6 g +21 h ::: a 7 + a 2 + a 4 + b 7 + b 2 + b 4 g +21 h w e ha v e g +21 h ( ( C 7 ))= a + b + c = ( a 1 + b 1 )+( a 3 + b 3 )+( a 5 + b 5 ) 3 35

PAGE 43

+ ( a 2 + b 2 )+( a 4 + b 4 )+( a 6 + b 6 ) 3 + + ( a 7 + b 7 )+( a 2 + b 2 )+( a 4 + b 4 ) 3 + c 7 g +21 h 3 + c 58 g 21 +58 h 1 : Therefore,for g =4, 8,20, w eha v e k ( ( C 7 ))= g +21 h ( ( C 7 )) j 58 g 21 k +58 h 1= j 58 k 21 k 1. 2 Theorem 3.6. k ( ( C 7 ))= 8 > > > > > > > < > > > > > > > : 7 for k =3 j 58 k 21 k 1 for k = g +21 h;g =4 ; 8 ; 20 ;h 0and in teger j 58 k 21 k otherwise Proof: Since f ( ( C 7 ))= f ( ( C 7 ))= 58 21 ,w eha v e k ( ( C 7 )) b k! f ( ( C 7 )) c = j 58 k 21 k Lemma3.2 sho ws 3 ( ( C 7 )) 7. By Lemma3.3, k ( ( C 7 )) j 58 k 21 k 1 for k = g +21 h andthegiv env aluesof g W euseinductiontosho wequalit y F or k = 1, 2, 5, 6, 7, 10, 11, 12, 15, 16, and 21, T able 7 sho ws that equalit y holds. F or k =3,4,8, and9, w eha v e k ( ( C 7 )) 2 ( ( C 7 ))+ k 2 ( ( C 7 ))= 8 > > < > > : j 58 k 21 k 1 for k =4 ; 8 j 58 k 21 k for k =3 ; 9 F or k =13, 14,17, 18,19, 20, 22,23, and 24,w eha v e k ( ( C 7 )) 12 ( ( C 7 ))+ k 12 ( ( C 7 ))= 8 > > < > > : j 58 k 21 k 1 for k =20 j 58 k 21 k otherwise F or k > 24, assume that the result holds for k 21. Since k ( ( C 7 )) k 21 ( ( C 7 ))+ 21 ( ( C 7 )),theresultholds for k> 24. 2 36

PAGE 44

k nodes 1 2 5 6 7 10 11 12 15 16 21 x 1 1 0 0 1 1 2 2 2 3 3 4 x 2 1 0 1 1 2 2 2 3 2 3 4 x 3 0 0 1 1 2 2 2 3 3 3 4 x 4 0 1 1 1 1 2 2 2 3 3 4 x 5 0 1 1 1 1 2 2 2 3 3 4 x 6 0 0 1 1 1 1 2 2 3 3 4 x 7 0 0 1 1 1 2 2 2 3 3 4 y 1 0 0 1 1 2 1 2 2 2 3 3 y 2 0 0 1 1 1 2 2 1 3 3 3 y 3 0 1 1 1 0 2 1 1 2 2 3 y 4 0 0 1 0 1 1 1 2 2 2 3 y 5 0 0 1 0 1 1 2 2 2 2 3 y 6 0 1 0 1 1 2 2 2 2 2 3 y 7 0 0 0 2 1 1 1 2 2 2 3 z 0 1 2 3 3 4 5 5 6 7 9 k ( ( C 7 )) 2 5 13 16 19 27 30 33 41 44 58 T able7: Thew eigh toneac hnode inak-cliqueof ( C 7 ). 37

PAGE 45

F or the next t w o proofs, w e will refer to t ypes of maximalindependen t sets of ( C 9 ) as follo ws: T ype X 3 : f x 1 ;x 3 ;x 5 ;y 1 ;y 3 ;y 5 ;y 7 ;y 8 g ; f x 2 ;x 4 ;x 6 ;y 2 ;y 4 ;y 6 ;y 8 ;y 9 g ;:::; f x 9 ;x 2 ;x 4 ;y 9 ;y 2 ;y 4 ;y 6 ;y 7 g T ype X 4 : f x 1 ;x 3 ;x 5 ;x 7 ;y 1 ;y 3 ;y 5 ;y 7 g ; f x 2 ;x 4 ;x 6 ;x 8 ;y 2 ;y 4 ;y 6 ;y 8 g ;:::; f x 9 ;x 2 ;x 4 ;x 6 ;y 9 ;y 2 ;y 4 ;y 6 g T ype Y : f y 1 ;y 2 ;:::;y 9 g T ype Z : f x 1 ;x 3 ;x 5 ;x 7 ;z g ; f x 2 ;x 4 ;x 6 ;x 8 ;z g ;:::; f x 9 ;x 2 ;x 4 ;x 6 ;z g Lemma3.4. 5 ( ( C 9 )) 12 : Proof: Therearethreecases. Case 1: c 3 : There are nine T ype Z independen t sets of ( C 9 ). Since a 1 + a 3 + a 5 + a 7 + c 5, a 2 + a 4 + a 6 + a 8 + c 5, ::: a 9 + a 2 + a 4 + a 6 + c 5, w eha v e a = a 1 + a 3 + a 5 + a 7 4 + a 2 + a 4 + a 6 + a 8 4 + + a 9 + a 2 + a 4 + a 6 4 9 5 c 4 : The T ype Y independen tset has w eigh t at most 5, therefore 5 ( ( C 9 ))= a + b + c 45 9 c 4 +5+ c 12 : Case 2: c 1 : Using the T ype X 4 independen t sets, since a 1 + a 3 + a 5 + a 7 + b 1 + b 3 + b 5 + b 7 5, a 2 + a 4 + a 6 + a 8 + b 2 + b 4 + b 6 + b 8 5, ::: a 9 + a 2 + a 4 + a 6 + b 9 + b 2 + b 4 + b 6 5, w eha v e 5 ( ( C 9 ))= a + b + c 9 5 4 + c 12 : 38

PAGE 46

Case 3: c =2 : Eac hT ype Z independen tsethasw eigh tatmost5,andtherefore con tainsatleastoneouternodeofw eigh t0. Sinceeac h x i isanelemen tof four T ype Z sets,thereare atleastthreezero-w eigh tedouter nodes. Case a: Two zer o-weighte d outer no des ar e se quential. F or an y t w o sequen tialouter nodes, thereis one T ype X 4 and one T ype X 3 independen t set that together con tain all nodes except z and the t w o sequen tial zerow eigh ted outer nodes. Since eac h independen t set is w eigh ted at most 5, forthis case, 5 ( ( C 9 )) 12. Caseb: Notwozer o-weighte douterno desar ese quential. Itiseasytosho w thatthereexistsbutonearrangemen tofthreenonsequen tialzero-w eigh ted outer nodes whic h does not violate a maxim um w eigh t of 5 on all T ype Z independen t sets; that is, the three zero-w eigh ted outer nodes m ust be equallyspaced around the cycle. Allotherouter nodes m ustbe at least1, toa v oidfallingin toCasea. Butthenon-zero-w eigh tedouternodescannot exceed1,elsew ecouldndT ype Z independen tsetsofw eigh tgreaterthan 5. Eac hzero-w eigh tedouternodeisanelemen tofaT ype X 4 independen tset whic hcon tainsthreeone-w eigh tedouternodes;therefore,itscorresponding innernodehasw eigh tatmost2. Ifan yinnernodecorrespondingtoazerow eigh ted outer node has w eigh t 0, then all other nodes except the cen ter 39

PAGE 47

are con tained in t w o T ype X 4 independen t sets, and then 5 ( ( C 9 )) 5+5+2 = 12. If one inner node corresponding to a zero-w eigh ted outer node has w eigh t 2, then in v estigation of the T ype X 4 independen t sets sho ws that the other t w o m ust ha v e w eigh t 1. Then to exceed a total w eigh t of 12 and to a v oid exceeding a maxim umw eigh t of 5 on the T ype Y independen t set, exactlyone other inner node m ust ha v e w eigh t 1; but allsuc hplacemen tsresultinasetofT ype X 3 withw eigh t6. Therefore,all inner nodes corresponding to zero-w eigh tedouter nodes m ustha v e w eigh t 1. The maxim umw eigh t on the T ype Y independen t set then dictates that the remaining inner nodes ha v e total w eigh t 2, but an y placemen t of the additionalw eigh tresultsinaT ype X 4 independen tsetwithw eigh t6. Therefore, 5 ( ( C 9 )) 12. 2 Lemma3.5. F or k = g +36 h ,wher e g =3 6 13 19 26 35 ,and h anonne gative inte ger, k ( ( C 9 )) j 97 k 36 k 1 Proof: Let q g represen tanin tegerassociatedwitheac h g ,suc hthat q 3 =2 ;q 6 = 3 ;q 13 =6 ;q 19 =9 ;q 26 =12 ; and q 35 =16. F or k = g +36 h ,itcanbesho wn that j 97 k 36 k 1= j 97 g 36 k +97 h 1. Therearet w ocases. Case 1: c q g +16 h UsingthenineT ype Z independen tsets,since a 1 + a 3 + a 5 + a 7 + c g +36 h a 2 + a 4 + a 6 + a 8 + c g +36 h ::: a 9 + a 2 + a 4 + a 6 + c g +36 h 40

PAGE 48

w eha v e a = a 1 + a 3 + a 5 + a 7 4 + a 2 + a 4 + a 6 + a 8 4 + + a 9 + a 2 + a 4 + a 6 4 9 g +36 h c 4 : Since the T ype Y independen t set has w eigh t at most g +36 h w e ha v e g +36 h ( ( C 9 ))= a + b + c 9 g +324 h 9 c 4 +( g +36 h )+ c j 97 g 36 k +97 h 1 : Case 2: c q g 1+16 h Using the nine T ype X 4 independen t sets, since a 1 + a 3 + a 5 + a 7 + b 1 + b 3 + b 5 + b 7 g +36 h a 2 + a 4 + a 6 + a 8 + b 2 + b 4 + b 6 + b 8 g +36 h ::: a 9 + a 2 + a 4 + a 6 + b 9 + b 2 + b 4 + b 6 g +36 h w e ha v e g +36 h ( ( C 9 ))= a + b + c j 97 g 36 k +97 h 1 : Therefore, for g = 3, 6, 13, 19, 26, 35, w e ha v e k ( ( C 9 )) j 97 g 36 k +97 h 1 = j 97 k 21 k 1. 2 Theorem 3.7. k ( ( C 9 ))= 8 > > > > > > > > > < > > > > > > > > > : 12 for k =5 j 97 k 36 k 1 for k = g +36 h;g =3 ; 6 ; 13 ; 19 ; 26 ; 35 ; h 0 and in teger j 97 k 36 k otherwise Proof: Since f ( ( C 9 )) = f ( ( C 9 )) = 97 36 then k ( ( C 9 )) b k! f ( ( C 9 )) c = j 97 k 36 k ByLemma3.4,w eha v e 5 ( ( C 9 )) 12,andLemma3.5sho ws k ( ( C 9 )) j 97 k 36 k 1for k = g +36 h andthegiv env aluesof g Inductionwillsho wequalit y F or k = 1, 2, 7, 8, 9, 12, 15, 16, 22, 25, 29 and 36, T able 8 sho ws that equalit y 41

PAGE 49

holds. F or k =3,4,5, 6,10, 11, 13,14, 17, 18, 19,20, 23, 24, 26,27, 30, 31, 33, 34, 35,38, 39,and 40, w eha v e k ( ( C 9 )) 2 ( ( C 9 ))+ k 2 ( ( C 9 ))= 8 > > < > > : j 97 k 36 k 1 for k =3 ; 6 ; 13 ; 19 ; 26 ; 35 ; 39 j 97 k 36 k otherwise F or k =21 ;! k ( ( C 9 )) 9 ( ( C 9 ))+ 12 ( ( C 9 ))= j 97(21) 36 k F or k =28, 32, 37, and 41, k ( ( C 9 )) 16 ( ( C 9 ))+ k 16 ( ( C 9 ))= j 97 k 36 k k nodes 1 2 7 8 9 12 15 16 25 29 36 x 1 1 1 1 1 2 1 2 3 3 4 5 x 2 0 1 1 1 1 2 2 3 3 4 5 x 3 0 0 1 1 1 2 2 2 3 4 5 x 4 0 0 1 1 1 1 2 2 3 4 5 x 5 0 0 1 1 1 2 2 2 3 4 5 x 6 0 0 1 1 1 2 2 2 3 4 5 x 7 0 0 1 1 1 1 2 2 3 4 5 x 8 0 0 1 1 1 2 2 2 5 4 5 x 9 0 0 0 1 2 2 2 2 5 4 5 y 1 0 1 0 1 0 2 2 1 4 4 4 y 2 0 0 1 0 1 1 1 1 3 3 4 y 3 0 0 1 1 1 1 1 2 3 3 4 y 4 0 0 1 1 1 2 1 2 3 3 4 y 5 0 0 1 0 1 1 1 2 3 3 4 y 6 0 0 1 1 1 1 2 2 3 3 4 y 7 0 0 1 1 1 2 2 2 3 3 4 y 8 0 0 0 1 2 1 2 2 1 3 4 y 9 0 1 1 2 1 1 3 2 2 4 4 z 1 1 3 4 4 5 7 7 11 13 16 k ( ( C 9 )) 2 5 18 22 24 32 40 43 67 78 97 T able8: Thew eigh toneac hnode inak-cliqueof ( C 9 ). F or k > 41, assume the result holds for k 36. Then since k ( ( C 9 )) k 36 ( ( C 9 ))+ 36 ( ( C 9 )),theresultholds for k> 41. 2 42

PAGE 50

Inthenextt w oproofs,w erefertothefollo wingt ypesofmaximalindependen t setsof ( C 11 )): T ype X 4 : f x 1 ;x 3 ;x 5 ;x 7 ;y 1 ;y 3 ;y 5 ;y 7 ;y 9 ;y 10 g ; f x 2 ;x 4 ;x 6 ;x 8 ;y 2 ;y 4 ;y 6 ;y 8 ;y 10 ;y 11 g ; :::; f x 11 ;x 2 ;x 4 ;x 6 ;y 11 ;y 2 ;y 4 ;y 6 ;y 8 ;y 9 g T ype X 5 : f x 1 ;x 3 ;x 5 ;x 7 ;x 9 ;y 1 ;y 3 ;y 5 ;y 7 ;y 9 g ; f x 2 ;x 4 ;x 6 ;x 8 ;x 10 ;y 2 ;y 4 ;y 6 ;y 8 ;y 10 g ; :::; f x 9 ;x 2 ;x 4 ;x 6 ;x 8 ;y 9 ;y 2 ;y 4 ;y 6 ;y 8 g T ype Y : f y 1 ;y 2 ;:::;y 11 g T ype Z : f x 1 ;x 3 ;x 5 ;x 7 ;x 9 ;z g ; f x 2 ;x 4 ;x 6 ;x 8 ;x 10 ;z g ;:::; f x 9 ;x 2 ;x 4 ;x 6 ;x 8 ;z g Lemma3.6. 5 ( ( C 11 )) 12 : Proof: Therearethreecases. Case 1: c 3 : There are elev en T ype Z independen t sets of ( C 11 ). Since a 1 + a 3 + a 5 + a 7 + a 9 + c 5, a 2 + a 4 + a 6 + a 8 + a 10 + c 5, ::: a 9 + a 2 + a 4 + a 6 + a 8 + c 5,w eha v e a 11 5 c 5 : TheT ype Y independen t sethasw eigh tatmost5,therefore 5 ( ( C 11 ))= a + b + c 55 11 c 5 +5+ c 12 : Case 2: c 1 : UsingtheT ype X 5 independen tsets,since a 1 + a 3 + a 5 + a 7 + a 9 + b 1 + b 3 + b 5 + b 7 + b 9 5, a 2 + a 4 + a 6 + a 8 + a 10 + b 2 + b 4 + b 6 + b 8 + b 10 5, ::: a 9 + a 2 + a 4 + a 6 + a 8 + b 9 + b 2 + b 4 + b 6 + b 8 5,w eha v e 5 ( ( C 11 ))= a + b + c 11+ c 12 : Case 3: c = 2 : Eac h T ype Z independen t set m ust con tain at least t w o outer nodes with w eigh t 0. Since eac h pair of outer nodes are con tained in at mostfourT ype Z independen tsets,andsincesomeduplicationma yoccur, thereareatleast v ezero-w eigh tedouter nodes. 43

PAGE 51

Case a: Two zer o-weighte d outer no des ar e se quential. Then all other nodes excludingthe cen terare con tainedin theunion of a T ype X 4 and a T ype X 5 independen tset. Then 5 ( ( C 11 )) 5+5+2=12 inthiscase. Case b: No two zer o-weighte d outer no des ar e se quential. Then the v e zero-w eigh tedouternodes m ustbespacedatleastoneapart. Butsinceall otherouternodes ha v epositiv ew eigh t,thereexistsaT ype Z independen t setwithw eigh tlargerthan 5,acon tradiction. Therefore, 5 ( ( C 11 )) 12. 2 Lemma 3.7. F or k = g +55 h wher e g =8 14 17 23 26 34 43 49 52 54 and h a nonne gative inte ger, k ( ( C 11 )) j 146 k 55 k 1 Proof: Let q g represen tanin tegerassociatedwitheac h g ,suc hthat q 8 =4 ;q 14 = 7 ;q 17 =8 ;q 23 =11 ;q 26 = 12 ;q 34 =16 ;q 43 = 20 ;q 49 =23 ;q 52 = 24 and q 54 = 25. F or k = g +55 h w eha v e j 146 k 55 k 1= j 146 g 55 k +146 h 1. Case 1: c q g +25 h Since eac h T ype Z independen t set has w eigh t at most g +55 h w eha v e a 11 g +55 h c 5 : SincetheT ype Y independen tsethas w eigh tatmost g +55 h ,w eha v e g +55 h ( ( C 11 ))= a + b + c 11 g +605 h 11 c 5 + ( g +55 h )+ c j 146 g 55 k +146 h 1 : Case 2: c q g 1+25 h Since eac h T ype X 5 independen t set has w eigh t at most g +55 h and eac h node is an elemen t of v e suc h sets, w e ha v e g +55 h ( ( C 11 ))= a + b + c 11 g +55 h 5 + c j 58 g 21 k +58 h 1. 44

PAGE 52

Therefore, k ( ( C 11 )) j 58 g 21 k +58 h 1= j 58 k 21 k 1. 2 Theorem 3.8. k ( ( C 11 ))= 8 > > > > > > > > > > > > > > < > > > > > > > > > > > > > > : 12 for k =5 17 or 18 for k =7 j 146 k 55 k 1 for k = g +55 h;g =8 ; 14 ; 17 ; 23 ; 26 ; 34 ; 43 ; 49 ; 52 ; 54 ; h 0and in teger j 146 k 55 k otherwise Proof: W e ha v e k ( ( C 11 )) b k! f ( ( C 11 )) c = j 146 k 55 k Lemma 3.6 sho ws 5 ( ( C 11 )) 12. Computational results sho w that 7 ( ( C 11 ))=17, ho w ev er,a theoreticalproofdoesnoty etexist. Lemma3.7pro v es g +55 h ( ( C 11 )) j 146 k 55 k 1 for the v alues of g giv enabo v e. By induction,w ewillsho w equalit y F or k =1, 2,9, 10, 11,16, 19, 20, 25, 28,37, 46 and 55, T able9 sho ws that equalit yholds. F or k =3, 4, 5, 6, 7, 8, 12, 13, 14, 15, 17, 18, 21, 22, 23, 24, 26, 27, 29 and 30, w eha v e k ( ( C 11 )) 2 ( ( C 11 ))+ k 2 ( ( C 11 ))= 8 > > < > > : j 146 k 55 k 1 for k =8 ; 14 ; 17 ; 23 ; 26 j 146 k 55 k otherwise F or k =31, 32, ::: ,36,38, 39, ::: ,45,47, 48, ::: ,54,56, 57, ::: ,62,w eha v e k ( ( C 11 )) 20 ( ( C 11 ))+ k 20 ( ( C 11 ))= 8 > > < > > : j 146 k 55 k 1 for k =34 ; 43 ; 49 ; 52 ; 54 j 146 k 55 k otherwise F or k > 62, assume that the result holds for k 55. Since k ( ( C 11 )) k 55 ( ( C 11 ))+ 55 ( ( C 11 )),theresultholdsfor k> 62. 2 Additionally ,computationalresults ha v e sho wn that ( C 13 ) is cliquishlyunstableat k =7 ; 9 ; and 18. 45

PAGE 53

k nodes 1 2 9 10 11 16 19 20 25 28 37 46 55 x 1 1 1 1 1 2 1 2 3 2 3 4 5 6 x 2 0 0 0 1 1 2 2 2 3 3 4 5 6 x 3 0 0 1 1 1 2 2 2 3 3 4 5 6 x 4 0 0 1 1 1 2 2 2 2 3 4 5 6 x 5 0 0 1 1 1 2 2 2 3 3 4 5 6 x 6 0 0 1 1 1 1 2 2 3 3 4 5 6 x 7 0 0 1 2 1 2 2 2 2 3 4 5 6 x 8 0 0 2 2 1 2 2 2 3 3 4 5 6 x 9 0 0 1 1 1 1 2 2 3 3 4 5 6 x 10 0 0 0 1 1 2 2 2 3 3 4 5 6 x 11 0 1 1 1 2 2 2 3 3 3 4 5 6 y 1 0 1 0 1 0 2 2 1 3 3 4 4 5 y 2 0 1 1 1 1 2 2 2 2 3 3 4 5 y 3 0 0 1 1 1 2 2 2 2 2 4 4 5 y 4 0 0 1 1 1 1 3 2 3 2 4 4 5 y 5 0 0 0 1 1 1 2 2 2 2 3 4 5 y 6 0 0 1 1 1 2 2 2 2 3 3 4 5 y 7 0 0 1 0 1 1 2 2 3 4 3 4 5 y 8 0 0 1 0 1 1 1 2 2 3 3 5 5 y 9 0 0 2 1 1 2 1 2 2 2 3 5 5 y 10 0 0 1 1 2 1 1 2 2 2 3 4 5 y 11 0 0 0 1 1 1 1 1 2 2 4 4 5 z 1 1 4 4 5 7 9 9 11 13 17 21 25 k ( ( C 11 )) 2 5 24 26 29 42 50 53 66 74 98 122 146 T able9: Thew eigh toneac hnode ina k-cliqueof ( C 11 ). 46

PAGE 54

REFERENCES 1. Fisher, D.C., \F ractional Colorings with Large Denominators", to app e ar in Journal of Gr aphThe ory 2. Fisher,D.C.,Marc han t,M.A.,Ry an,J.,\AColumnGeneratingAlgorithm for Finding F ractional Colorings of Random Graphs", Congr essus Numerantium ,89: 245-253. 3. Fisher,D.C.,\P eriodicitiesinDiscreteSystems", pr eprint 4. Larsen,M.,Propp,J.,andUllman,D.,\TheF ractionalChromaticNum ber ofaGraphandaConstructionofMycielski" toapp e arinJournalofGr aph The ory 5. Stahl,S.,\ n -tupleColoringsandAssociatedGraphs" JournalofCombinatorial The ory ,(B)20(1976) 185-203. 6. Stahl,S.,\ n -tuple Colorings oftheGrotzc hGraph", pr eprint 47