Citation
The conditional chromatic number of a graph

Material Information

Title:
The conditional chromatic number of a graph
Creator:
Casey, Karen Lee
Publication Date:
Language:
English
Physical Description:
v, 31 leaves : illustrations ; 29 cm

Subjects

Subjects / Keywords:
Graph theory ( lcsh )
Graph theory ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 30-31).
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 Karen Lee Casey.

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:
30696495 ( OCLC )
ocm30696495
Classification:
LD1190.L622 1990m .C37 ( lcc )

Downloads

This item has the following downloads:


Full Text
THE CONDITIONAL CHROMATIC NUMBER OF A
GRAPH
by
Karen Lee Casey
B. S., Metropolitan State College of Denver, 1990
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Applied Mathematics
1993


This thesis for the Master of Science
degree by
Karen Lee Casey
has been approved for the
Department of
Mathematics
by


Casey, Karen Lee (M.S., Applied Mathematics)
The Conditional Chromatic Number of a Graph
Thesis directed by Professor Kathryn Fraughnaugh
ABSTRACT
The conditional chromatic number of a graph is the assignment of
colors 1... k to the nodes such that each color class V\... Vk induces a sub-
graph with property P. The conditional chromatic number with respect to
the property that a graph have no cycle for a fixed j is studied, and a survey
of known results is given. New results for this property are given when the
number of edges in a graph is large.
This abstract accurately represents the content of the candidates
thesis. I recommend its publication^
Signec
Kathryn Fraughnaugh
m


DEDICATION
To Sean Dargen
the Systems Administrator of DARGENET
for all of your technical and emotional support.


ACKNOWLEDGEMENTS
I would like thank Dr. Kathryn Fraughnaugh for the time and energy
she spent assisting me in this endeavor for which I am very grateful. Addi-
tionally, I would like to thank Dr. David Fisher, and Dr. Rich Lundgren for
their guidance and support. Finally, I would like to say THANK YOU to all
of my friends for your encouragement and support during the last year and a
half!
v


CONTENTS
CHAPTER
1 INTRODUCTION.......................................... 2
1.1 Definitions and Notation............................ 3
1.2 History............................................. 6
2 PRELIMINARY RESULTS..................................... 9
2.1 Seven Properties of x(G,-iCj)...................... 9
2.2 Implications for x(G,-iCj) from x(^>-Pa)........... 11
2.3 General Results for ->Cj .................. 18
3 NEW RESULTS............................................ 20
3.1 Ores Theorem...................................... 20
3.2 The Value of x(G, ->Cj) When |_E( 3.3 Future Directions ................................. 28
References.................................................... 30


CHAPTER 1
INTRODUCTION
The chromatic number of a graph G, is defined to be the smallest
number of colors needed to color G, such that no two adjacent vertices have
the same color [13]. Analogously, the chromatic number can be defined as the
minimum n, for which there exists an n-partition of the vertices, such that
each induced subgraph contains no complete graph on two vertices. Each set
of the partition of the vertices is called a color class.
The chromatic number can be generalized in several different ways.
For example, the nodes of a graph can be colored such that the subgraphs of
G formed from the color classes contain no path on a fixed number of vertices.
Another generalization is to color the nodes of G such that the subgraphs
contain no cycles. In fact, any graph theoretical property can be used to
generalize the chromatic number.
The generalized chromatic number is defined as the minimum number
of colors needed to color the nodes of G such that every subgraph of G induced
by a color class has property P (various authors, see [1]). This generalization to
any property is now referred to as the conditional chromatic number of a graph
[12]. In the following sections we will discuss the history of the conditional
chromatic number, relate known results to the property of containing no cycles,
and prove new results for the value of the conditional chromatic number with
respect to the property of forbidding cycles of a fixed length.


1.1 Definitions and Notation
The graphical definitions and notation of [13] will be used, except
that a graph G = (V, E) will refer to vertex set V, with |V\ = n = n(G), and
edge set E, with \E\ = e = e(G) in addition to nodes and lines. Every graph G
will be simple without loops. A cycle (or j-cycle) Cj is a simple cycle on j > 3
nodes.
Define a graph G to be planar if it can be embedded in a plane S such
that when it is drawn on S no two edges intersect. A graph G is outerplanar
if it can be embedded in the plane so that all its vertices lie on the same face.
Let mG denote m disjoint copies of the graph G. The minimum vertex degree
and the maximum vertex degree will be denoted 6(G) and A(G) respectively.
A cycle is Hamiltonian if it has no repeated vertices and contains all of the
vertices of G. A graph is Hamiltonian if it contains a Hamiltonian cycle [23].
For A C V, define N(X) = {u|uu £ E for some v E X}, N[X] =
N(X) U {A-}, and H(X) = V N[X]. When A is a single vertex x, the
preceding definitions correspond respectively to the usual definitions of the
open neighborhood of x, closed neighborhood of x, and non-neighbors of x.
Define the girth g(G) to be the length of the shortest cycle in G.
The chromatic number of a graph G is the smallest integer, x(G), so
that the vertices of G can be assigned the numbers 1,2, ...,x(G) in such a
manner that each color class K', 1 < i < xC^)? induces a subgraph (Vi) that
consists entirely of isolated points. If S is a subset of either E or V, then (S)
is the subgraph of G induced by S. A coloring is said to be proper if no two
distinct adjacent vertices have the same color.
As an example, x(As) = 5, because each color class can contain
3


exactly one vertex (see Figure 1). If any color class contained more than
one vertex, the graph induced from the color class would contain at least two
vertices that are adjacent (every vertex is adjacent to every other vertex in a
complete graph).
I
Figure 1. Labeling the vertices as shown above, we can partition
the vertices as V\ = {1}, V£ = {2}, V3 = {3},V4 = {4} and Vs = {5}.
Each graph induced by Vi, 1 < i < 3, contains no K2- If any partition
contained more than one vertex, the induced graph would contain a
K2. Therefore, x(G) = 5.
The conditional chromatic number with respect to a graph theoretical
property P, denoted x(G,P), is the minimum n for which there exists an re-
partition, V = UK such that for each i, the induced graph (VJ) is in P.
If P is the property that the subgraph induced from each color class
be cycle free, we will denote the conditonal chromatic number as x{G,Pa)-
This number is also referred to as the point arboricity of a graph.
If P is the property that a given graph F be forbidden to be induced
by any subset of the vertices in VJ-, the conditional chromatic number is denoted
as x(G, ~>F). For the remainder of this paper x(G, ~>F) will also be referred to
as a -iF-coloring, -iF-chromatic number, and F-Free chromatic number. In any
case where P is ambiguous, we will let P-,p denote the property of forbidding
4


the subgraph F. The property of forbidding cycles of a fixed length, denoted
x(G, will be studied in the remainder of the paper. Define a graph G to
be vertex P k critical if and only if x(G, P) = k, but x(G v,P) < k for
all 17 V(G).
As an example of x(G,~>Cj), let G = K5, the complete graph on
five vertices shown in Figure 1. The conditional chromatic number of K5
with respect to the property of forbidding cycles, yields the following values of
x(G,->Cj), for differing values of j.
If j = 3, then x(G, = 3, because each color class can consist of
no more than two vertices (if a class contained three vertices the corresponding
graph would induce a K$ because G is complete). With a maximum of two
vertices in each color class, we need to partition the vertices of G into three
classes (two classes consisting of two vertices, and one class consisting of one
vertex).
If j = 4, then x(G, -'C4) = 2, because each color class can consist
of no more than three vertices (same reasoning as above). We partition the
vertices into two color classes, one consisting of three vertices, and the other
consisting of the remaining two vertices of G.
If j = 5, then y(G, ~>Cs) = 2, because each color class can consist
of no more than four vertices (same reasoning as above). We partition the
vertices into two color classes one of two ways shown in Figure 1: one color
class can consist of three vertices and the other color class can consist of the
remaining two vertices, or one color class can consist of four vertices and the
other color class can consist of the remaining vertex. Labeling the vertices as
in Figure 1, the vertices can be partitioned as V\ = {1,2,3}, V2 = {4,5} or
5


V\ = {1,2,3,4}, V2 = {5}. The graph induced by Vi, 1 < i < 2, contains no
Cs.
If j = 6, then x(G, -iC&) = 1, because each color class can consist of
five vertices without containing a Cq.
In Chapter 2 we will prove that if the size, j, of the cycle being
forbidden is larger than the number of vertices of G, x(G,->Cj) = 1.
1.2 History
The first published articles about conditional chromatic numbers ap-
peared in 1968 in [8], [17], [10], and [9]. The definitions and notation used in
these papers was not consistent, so it will be clarified when necessary, and re-
stated using the notation of [12]. The following is an overview of these papers,
emphasizing results related to the conditional property of forbidding cycles of
a fixed length.
In [8] the conditional chromatic number is studied with respect to the
property that each induced subgraph contain no path of a fixed length. The
authors denoted this number as Xn(G). Using the contemporary notation, these
numbers would be denoted x(G, ~'Pj) for j fixed. The authors showed that for
every positive value of j, there exists a planar graph G such that x(G, ->Pj) = 4.
This proves that no result stronger than a Four Colour Theorem is possible
(see paper for details).
As another example, in [17] Hedetniemi defined a P-set of G to be a
subset of the vertices of G such that the subgraph induced by S has property
P. He also defined a P-coloring of a graph to be, an assignment of colors to
the vertices of G, such that for any given color the set of vertices having this
color is a P-set. The definition of a P-set is equivalent to that of a color class
6


inducing a subgraph having property P. A P-coloring is equivalent to a proper
coloring with respect to property P. Hedetniemi found an upper bound for the
value of the chromatic number with respect to the property that each color
class be cycle free. This property is also called the point arboricity of a graph,
and as we defined in the previous section, is denoted x(G, Pa). Hedetniemis
results are strengthened in [10] and [9] and will be used below to determine
bounds for x(G,->Cf).
Another example of a property that has been studied, is the prop-
erty P that each V, contain no complete graph on three vertices, denoted
x(G, ->K3) = x(G, The authors in [16] present a conjecture for the value
of x{G-> -,Ar3), when G is a planar graph, and prove a result about x(G, ^Ks)
when G is a maximal planar graph. In a sense, this paper bridged the gap
between the 1968 results, and the 1985 re-emergence of conditional chromatic
research.
In the paper titled Conditional Colorability in Graphs, Harary [12]
provided notational clarification, standardization, as well as a comprehensive
survey of nine known results for generalized chromatic numbers. Harary used
these new definitions to write the standard chromatic number of a graph as
x(G,-i^)- Hararys definitions and notational standard are used throughout
the remainder of this paper (see previous section).
More recent terms referring to the conditional chromatic number of a
graph include: the general chromatic number [26], the Pk-chromatic number
[6], the P chromatic number [1], the F free chromatic number [21], a -iG k-
coloring [5], and a generalized family of colorings [4]. For a survey of conditional
colorability research, see [12] and [1]. The table below summarizes some of
7


the conditional properties that have been studied, and their corresponding
references.
A Table of Conditional Properties
Color Class Property Reference
disconnected or trivial Hedetniemi (1968) [17]
acyclic Hedetniemi (1968) [17]
contains no Pj for fixed j Chartrand, Geller, Hedetniemi (1968) [8]
contains no Kj for fixed j Sachs, Schauble (1968) [24]
minimum vertex degree > j Kramer, Kramer (1969) [18]
for fixed j Lick, White (1970) [20]
contains no Ks .Harary, Kainen (1977) [16]
complete or empty Lesniak Foster, Straight (1977) [19]
contains no (u,v) with distance(it, v) = j Neeralagi, Venkatachalam (1977) [1]
maximum vertex degree < j Harary, Fraughnaugh (1985) [14], [15] Andrews, Jacobson (1985) [2], [3]
disjoint union of Domke, Laskar,
complete subgraphs Hedetniemi, Peters (1986) [11]
contains no (u, v) with distance (u, v) < j Baldi (1990) [4]
j independent for fixed j Sampathkumar (1993) [25]
has no cycles for fixed j Casey, Fraughnaugh (1993) [7]
8


CHAPTER 2
PRELIMINARY RESULTS
This chapter begins the study of the conditional chromatic number
with respect to property, P = ~'Cj, for a fixed j > 3. The first theorem
states seven basic properties of x(G, ~'Cf) that follow from definitions. These
properties will be used throughout the remainder of the paper. In the second
section of this chapter, established conditional chromatic number results for
point arboricity are used to prove bounds for the value of x(Gr, In the
third section, general conditional chromatic number results for properties that
are hereditary are restated specifically for x(G, -iCj).
2.1 Seven Properties of x(G,-iCj)
Although all of the properties in this theorem are straightforward,
they will be important to the establishment of new results in Chapter 3. Note
that properties (b), (d), (f), and (g) follow from observations of previous au-
thors [12].
Theorem 2.1.1
(a) x(K^Cj) = f^l .
(b) If H is a subgraph of the graph G, then x(H-> ~^Cj) < x(G, ~'Cj).
(c) For every graph G, x(G,~>Cj) < \n/(j 1)].
(d) If G is disconnected with components
Gi, G2,..., GT, then x(G, -iCj) = maXi{x(G,-,


(e) x(G,~>Cj) = 1 if and only if G contains no Cj. Consequently, for n < j,
x(G,-*Cj) = I-
r/;x(G,-Q) (g) For the complete bipartite graph G = Kp>q with p < q,
x(G^Cj)
1 if j is odd or j > 2p
<
2 if j is even and 4 < j <2p
Proof.
(a) A proper coloring of Kn will consist of color classes Vi ... 14 such that each
(Vi) is a subgraph of Kn. Each induced subgraph of a complete graph is
complete. Therefore, every color class that consists of more than j 1
vertices will contain an induced Cj. Every color class that consists of j 1
vertices or fewer will not contain a Cj. This implies the maximum number
of vertices in each color class is j 1. Therefore the total number of color
classes needed to color Kn is
0-i)
= x(-Kn,->Cj).
(b) If G is complete the result follows from (1) above. Otherwise, from the
definition of x(G) we know that x(G, ~'Cj) is the minimum number of
color classes needed to properly color the vertices of G. Since H is a
subgraph of G, coloring the vertices of H as we did with G will yield a
proper coloring of H. Since H may contain fewer vertices and edges than
G, it may be possible to color H with fewer than x(G,~>Cj) colors. In any
case x{H,~>Cj) can be colored with xiG^Cj) or fewer colors. Therefore
X(H^Cj) (c) Every graph G is either complete, or the subgraph of a complete graph.
If G is complete the result follows by (1) above, if G is not complete, then
the result follows by (2) above.
10


(d) Each Gi is a subgraph of G so by (2) above max,{x(G,-, -,Cj)} < x(G, ~>Cj).
We now must show max,{x(G,-, ~'Cj)} > x(G, ~>Cj). Assume
max,-{x(Gi, -iCy)} = k. Then every other component of G can be prop-
erly colored with < k colors. Since all components are disconnected from
each other, the vertices from each non-maximal component can be in-
cluded in the k color classes of the maximal component without creating
a Cj. Then the number of colors needed to color G is no more than
k = maxj{x(G,-, Cy)}.
(e) x(G, ~'Cj) = 1 O every vertex of G can be colored the same color <=>
G contains no Cj If n < j then G can not contain a Cj. Following the
argument backwards implies x(G,Cj) = 1.
(f) It follows from the definitions of x(G) and x(G, Pa) that a coloring that
satisfies the former, will satisfy the latter, and a coloring that satisfies the
latter will not necessarily satisfy the former, therefore x(G, Pa) < x(G).
Similarly, x(G, ->Cj) < x(G, Pa).
(g) If G is the complete bipartite graph, then G contains no odd cycles but
contains even cycles of every length j for j up to and including 2p. The
graph can be colored with two colors by assigning a color to each of the
two sets of the bipartition.
2.2 Implications for x(G, ->Cj) from x(G, Pa)
In 1968 Hedetniemi [17], Chartrand and Kronk [9], and Wall [10],
studied the conditional property Pa that each color class have no cycles. The
.Pa-chromatic number is also called the point arboricity. From Theorem 2.1.1(f)
it follows that an upper bound on the point arboricity for a family of graphs is
11


also an upper bound for the ~iCj-chromatic numbers for the given family and
each value of j > 3. This section examines the major results of Pa-chromatic
numbers and translates them into -iCj-chromatic number results.
The Pa-chromatic number results of this section are divided into three
parts, the first examines upper bounds for the Pa-chromatic number, the second
improves these results if G is planar (or outerplanar), and the third consists of
more recent Pa-chromatic number results.
The study of Pa-chromatic numbers began with a series of papers in
1968 in which the authors proved upper bounds for x{Gi Pa)- All of the results
below that are attributed to [10] and [9] can be similarly attributed to [17].
Chartrand, Kronk and Wall [10] interpreted the point arboricity (Pa)
of a graph as a coloring number since Pa(G) is the minimum number of
colors needed to color the vertices of G such that no cycle has all of its vertices
colored the same. Using an inductive argument on the number of vertices of a
graph they proved the following theorem.
Theorem 2.2.1 For any graph G,
X(G,P.)< 1 +-f-(g)'
For complete graphs Theorem 2.2.1 is tight because the maximum
number of vertices in any color class is two any more and the graph induced
by the vertices of the color class consists of a cycle of length three. Therefore,
~n 1 + (n 1) 1 + A(G)"
2 2 2
X(K.,P.) =
On the other hand, for planar graphs with large maximum degree this
bound is not very strong. For example the complete bipartite graph Ki,w is
planar with A(G) = 10, so from Theorem 2.2.1 x(G, Pa) < = 6. But
12


ICi.10 contains no cycles so x(G, Pa) = 1. As we will see below this bound can
be improved for planar graphs!
In 1969 Chartrand and Kronk [9] established an upper bound similar
to that given in Theorem 2.2.1 above. The two main theorems of [9], and a
brief justification of each are stated below.
Theorem 2.2.2 For any graph G,
X(G,Pa)< 1 +
'A(G9
2
The proof of Theorem 2.2.2 relies on the fact that there exists an in-
duced re-critical (see section 1.2) subgraph H of G. Additionally, the minimum
vertex degree of H is less than or equal to the maximum over all minimum
degrees of subgraphs of H. Using the re-critical property the result follows, see
[9] Theorem 1 for details. Note that Theorem 2.2.1 and 2.2.2 produce the same
bound when A(G) is even, but when A(G) is odd the bound in Theorem 2.2.2
is smaller.
The next theorem improves the upper bound for x{G,Pa) in the case
that G is non-regular, i.e., every vertex is not of the same degree.
THEOREM 2.2.3 If G is a connected and non-regular graph, then
x(G,P.)< 1 + A(G)
Theorem 2.2.1 and 2.2.3 immediately give the following upper bounds
for the -iCj-chromatic numbers.
THEOREM 2.2.4 For all j > 3 and for all graphs G,
x{G, ~>Cj) <
l+.A(g)~
2
If in addition G is non-regular and connected, then
x{G, ~,Cj) < 1 + A(G)
13


Note that in the previous two theorems we must assume G is a con-
nected graph otherwise the graph in Figure 2 would be a counterexample.
Figure 2. This graph consists of disconnected components K$ and
K-i- From Theorem 2.2.4 x(G, ->63) = 1, but clearly xCG^Ca) = 2
because one of the disconnected components of G is C3.
Although the complete graphs demonstrate that the inequality in
Theorem 2.2.4 is best possible for Pa, the complete graphs only demonstrate
that it is best possible for P-,c} when j = 3. For example, consider x(G, ->£4)
with G = K$. From Theorem 2.2.4 x(G, 1C4) < [^| = 3. This bound is
not tight because x(G, -1C4) = 2 (see the discussion at the end of Chapter 1,
Section 2).
We do not yet know a family of graphs for which the bound is tight
when j > 4. It is possible that no such family exists.
It is easy to conjecture that Theorem 2.2.1 can be improved for pla-
nar graphs because x(G,Pa) < x(^)> see 2.1.1 (f), and from the Four Color
Theorem, see [10], x(Gi Pa) < 4. In fact, x(G, Pa) < 3 for planar graphs, which
was proved in [10],[9] and [17].
THEOREM 2.2.5 For every planar graph x(G,Pa) < 3.
14


To prove Theorem 2.2.5, Chartrand and Kronk observed that every
induced subgraph of a planar graph is planar, and that every planar graph
contains at least one point of degree 4 or less. From Theorem 2.2.2 x(G, Pa) ^
1 + 1 and the result follows.
Chartrand and Kronk used the dual of the Tutte graph as an example
to show equality for Theorem 2.2.5.
%
Figure 3 The Tutte Graph. The dual of this graph has point
arboricity three.
Figure 3 is a Tutte graph, a planar graph whose dual G* has point
arboricity 3. The dual of a graph G can be constructed as follows: each region
(labeled Ri..Rk) of G is represented by a vertex in G*, and an edge exists
between two vertices in G* if and only if the corresponding regions of G are
adjacent. The proof that G* has point arboricity three is as follows.
15


We will show it takes exactly three colors, to color the regions of G
(and thus vertices of G*).
Assume we can color G with two colors, and label the regions of G as
shown in Figure 3. No three of and R3 can be colored the same color
without inducing a C3, So color two of i?i, R2, R3 with color a and color the
remaining region b. The region, i?4, outside G is adjacent to R\, R2 and i?3.
If R4 were colored with color a, then G* would contain a C3, so it must be
colored with color b.
Assume BWOC that R5 is adjacent to the two large regions colored
with color a. It follows that R5 must be colored with color b, otherwise, G*
would contain a C3. Similarly, at least one of Re or R7 would have to be colored
with color b. Assume R7 is colored b, this forces Re to be colored a. Then Rg
cannot be a, so color it b. Since both Rg and R4 are colored b, this forces Rg
to be a, and thus Rio to be b. If Ru is colored a then together with R\, R2,
Re, and Rg they form a C5 in G*. Otherwise, if Ru is colored b, then together
with R7, and Rg they form a C3 in G*. So Ru must be colored with a third
color.
Similar reasoning is used for the case of R5 adjacent to Ri colored a
and R2 colored b.
Because the graph is symmetric, these two cases yield the minimal
number of colors needed color G*, which is three. Figure 3 shows G colored
with three colors.
Another class of graphs studied in [17] and [9] is the subclass of planar
graphs known as outerplanar graphs. Any planar graph is also outerplanar if
it can be embedded in a plane such that all of its vertices lie on the exterior
16


region. It can be shown that if a graph is outerplanar then x(G) < 3, see [17].
Additionally, every outerplanar graph contains at least one vertex of degree less
than or equal to two, see [13]. These two observations, along with an inductive
argument proves the following theorem.
THEOREM 2.2.6 IfG is outerplanar, then x{G, Pa) < 2.
The following implications for x(G, ~'Cj) are immediate from the
above results.
Theorem 2.2.7
(a) If G is a planar graph, then x(G, -,Cj) 5: 3 for all j > 3.
(b) If G is an outerplanar graph, then x{G, ~'Cf) < 2 for all j > 3.
As a final note, the first two parts of the following theorem are from
Sampathkumar and Venkatachalam [26] and are upper and lower bounds for
the point arboricity and thus a bound for x(G, -|Cj). These results may lead
to a future direction and are stated here for completeness.
Theorem 2.2.8
(a) For every graph G, y/n < x(G, Pa) + x{G, Pa) < \{n + 3).
(b) For every graph G, f < x(G,Pa)x(G,Pa) < [j(n + 3)]2
Theorem 2.2.9
(a) For every graph G, x(G, -'Cj) + x{G, ~>Cj) < \{n + 3).
(b) For every graph G, x{G,^Cj)x{G,^Cj) < [J(n + 3)]2
The upper bound given in Theorem 2.2.9 (a) above is tight for G = Kn
when n is odd and j = 3. We can prove this as follows: From Theorem 2.1.1
(a) = [(j^l = ff]. Sincen is odd. [j] = !=H.
Since G is complete, G is completely disconnected thus x(G, ^Cz) =
x(Kn^C3) = 1. Therefore x(G,-'Ci)+x(G,-.C,-) = x(ff,-G>)+x(tf,-C3) =
17


+ 1 = |(n + 3).
We have been unable to find a family of graphs for which the upper
bound in Theorem 2.2.9 (b) is tight and conjecture this bound can be improved
upon.
2.3 General Results for ->Cj
This section relates more recent results about conditional chromatic
numbers. In the paper On Generalized Graph Colorings by Brown and
Corneil [6], several general results are proved about the conditional chromatic
number of a graph, given the property P under investigation is hereditary. A
property is hereditary if and only if when a graph G has P, then any subgraph
H of G has P. The property of forbidding cycles of a fixed length j is hereditary
because if a graph does not contain a cycle for a fixed value of j, then none
of its subgraphs contain a cycle for a fixed value of j. Therefore, each of the
results in [6] holds true for x(G,~>Cj).
Following the results of Mynhardt and Broere [21], Brown and Corneil
[6] investigated the existence of graphs with arbitrarily high P-conditional chro-
matic number. All of the Brown and Corneil results summarized in this section
assume P is non-trivial and hereditary.
Theorem 2.3.1
(a) If P is non-trivial (G ^ P), and hereditary then there exists a graph G
with x(G, P) = k for all k > 1.
(b) Every P-conditional chromatic graph contains a vertex P k-critical sub-
graph.
(c) Any P-conditional chromatic graph contains a vertex P t-critical subgraph
for all l < x(G, P).
18


A proof for part (a) was originally proved by Folkman in 1970. An-
other proof was given using Ramsey theory for hypergraphs in a Brown and
Corneil manuscript. A somewhat less complicated proof of (a) appears in [6].
Part (b) is proved using the definition of vertex critical and the properties of
vertex critical graphs. Brown and Corneil proved part (c) using an induction
argument, on the critical vertex.
Another question addressed in [6] concerns the number of ways the
vertices of G can be uniquely colored. Unique colorings exclude permutations
of either the vertices or the colors. Although these results are applicable to
the general theory of conditional chromatic numbers, they are not applicable
to the specific conditional chromatic number with respect to forbidding cycles
of a fixed length and will be omitted.
Additionally, Sampathkumar [25] extended the Brown and Corneil
results with respect to the chromatic number of critical graphs. At this time,
analogous results do not exist for conditional chromatic numbers of critical
graphs.
19


CHAPTER 3
NEW RESULTS
In this chapter a result of Ores together with the results established
in the preceding chapter provide a basis for determining the value of _,Cj)
when G has a large number of edges.
3.1 Ores Theorem
Following are two standard results of Ores [22] about Hamiltonian
graphs, which are necessary for the next section.
THEOREM 3.1.1 In a graph G with n > 3, if for every pairu and v of nonad-
jacent vertices deg(u) + deg(v) > n, then G is Hamiltonian.
THEOREM 3.1.2 If G is a graph with n > 3 and |U(Cr)| > (n2 3n + 6)/2,
then G is Hamiltonian.
Proof. Assume \E(G)\ > (n2 3n + 6)/2. Since every graph on n nodes
is either a complete graph, or subgraph of a complete graph, the maximum
number of edges G is missing can be computed by subtracting (n2 3n + 6)/2
from \n(n 1) (the number of edges in Kn). The result of this computation
is n 3. So there are at most n 3 edges missing from G.
Assume BWOC there exists (u,v) a pair of non adjacent vertices in G
such that deg(u) + deg(v) < n. This implies the total number of edges missing
from G is at least n 1 a contradiction. Therefore, from Ores Theorem above,
G is Hamiltonian.


3.2 The Value of x{G,->Cj) When |^(G)| Is Large
In this section we investigate the value of x(G, ~'Cj) when the number
of edges in G is large [7].
Now we present a series of theorems in which the value of x(G, ~'Cj)
is given when G is missing a small number of edges. First we find the value of
the conditional chromatic number when G is missing j 3 or fewer edges.
Theorem 3.2.1 If e(G) > (!j) (j-3), then x(G,->Cj) = \n/(j -1)] for all
j > 3-
Proof. From Theorem 2.1.1(c), it follows that x{G,-^Cf) < \n/(j 1)]. Sup-
pose by way of contradiction that G is ->(7;-colored with fewer than \n/(j 1)]
colors. Then some color class A contains at least j nodes. Let B C A with
|B\ = j. Then e(B) > j(j l)/2 (j 3) = (j2 3j + 6)/2. It follows
from Theorem 3.1.2 that B is Hamiltonian. Therefore A contains a j-cycle, a
contradiction. Thus x(G,- Next we want to find the values of x(G, ~^Cf) when G is missing
j 2 edges. On the way to this result, we show that when the complement
of G contains edges that induce particular types of subgraphs, the values are
readily found.
THEOREM 3.2.2 If G is a graph for which (E(G)) = Ki,m for j 2 < m <
n l, then x(G, Cj) = |"(n 1 )/(j 1)] for all j > 3.
Proof. Let v be the node of degree m in the subgraph of (E(G)) induced by
the K\,m- Let A be a color class in a ->Cj-coloring of G with k colors. If v
is not in A, then A induces a complete subgraph of G and hence contains an
|A|-cycle. Thus, every color class not containing v has at most j 1 elements.
If v 6 A and |A| > j + 1, then A {u} induces a complete graph on j nodes and
21


hence contains a jcycle. Thus the color class containing v contains at most
j elements. Since there are k 1 color classes with at most j 1 elements and
one color class with at most j elements, n < (k l)(j 1) + j = k(j 1) + 1.
Thus x(G,^Cj) >k>\(n- 1 )/(j 1)].
On the other hand, we can color V as follows: Color v and j 2 of its
non-neighbors plus one additional node with color 1. Since the degree of v in
this color class is at most 1 and the class contains j nodes, clearly this class has
no j-cycle. Color the remaining nj nodes so that no color class contains more
than j l nodes. This gives a -iQ-coloring of V with 1 + [(n j)/(j 1)] =
\(n 1 )/(j 1)] colors. Thus we have shown x(G, ~'Cj) = f(n 1 )/(j 1)].

THEOREM 3.2.3 If (E(G)) = mK2 where 1 < m < [n/2j, then x(G,~>C3) =
Pt1!-
Proof. Let M = E(G) and let A be a color class in a minimum -1 (73-coloring C
of G. Since any subgraph induced by five nodes is missing at most two edges of
M and therefore must contain a triangle, |j4| < 4. If |A| = 4, then in order that
A be (73-free, A must be missing exactly two edges of M. Also if |A| = 3, then
A must be missing exactly one edge of M. Let a be the number of color classes
in C with four nodes; 6, the number with three nodes; and c, the number with
no more that two nodes. Then b = m 2a r for some nonnegative integer r
and since C is a minimal coloring, c = []. The number of colors in C is
a + b + c, so that
x(G,-C3) = a+6+r-1 = r21
2a (m 2a r)^ n m + r ^
22


Now we want to produce a ->(73-coloring for G with py2-] colors. Let
n = 2m + s for s > 0 and suppose first that m is even. Form m/2 classes of
four nodes, each class consisting of the endpoints of two edges of M. From
the remaining nodes, form \s/2] classes with at most two nodes. This gives a
coloring with
m [s + m ~n m'
1 2 1 1 2 2
colors. Now suppose m is odd. Form (m l)/2 classes of four nodes, each
class consisting of the endpoints of two edges of M. If s = 0, then take the
remaining class to be the two endpoints of the remaining edge of M. We get
22yi +1 = = [y] = colors. If $ > 1, then form one additional class
containing the remaining edge of M and any other of the remaining nodes and
[(s 1)/2] classes of at most two nodes. Then we have used +1 + py] =
r=?l = colors.
The next theorem simply confirms that missing m independent edges
from G does not reduce the value of x(G, -|(7j) when j > 4.
THEOREM 3.2.4 If (E(G)) = mK2 where 1 < m < \n/2\, then xi^^Cj) =
f jrrl for al1 j > 4-
Proof. Let A be a set of j nodes and let v G A. Since the missing edges are in-
dependent, at most one of these is incident to v. Hence deg^A)(v) > j 2 > j/2
for j > 4. It follows from Theorem 3.1.1 that A induces a Hamiltonian sub-
graph, i.e., a subgraph with a j-cycle, and hence that no color class contains
more than j 1 nodes. Thus x(G, Cj) > \n/(j 1)] and the equality follows
from Theorem 2.1.1(c).
However, when G is missing disjoint copies of K3, the values of the
-iCj-chromatic numbers may be smaller for j > 4.
23


THEOREM 3.2.5 If {E(G)) = mK3, where 1 < m < |n/3J and n = 3m + s,
then
I Tfl if 0 < s , ->C4) <
[ r^i ifs > m
Proof. Let A be a color class in a minimum -iC^-coloring C of G. Suppose
|A| > 5. Then in the subgraph B induced by any five nodes of A, the maximum
number of missing edges is four and they must occur in Ks + K^. But even in
this case B contains a 4-cycle. Thus |A| < 4. If |A| = 4, then in order that A
be CVfree, A must be missing three edges in a single copy of K3. Clearly, if
|A| < 3, A contains no 4-cycle.
Let a be the number of classes of order four and b the number of order
three or smaller. Since each color class of order four must be missing the edges
of a K3, a < m. In addition, since C is minimum, b = so that
, rn 4an rn a.. rn mn
X(G, -1C4) = a + b = a + [-] = fr] > [r1.
Now we want to produce a minimum -iCVcoloring. Let n = 3m + s
for some nonnegative number s and let S be the set of nodes that are not an
endpoint of an edge in a K3. If 0 < s < m, then each of the nodes in S can
be added to the three nodes in a K$ to form a color class of order four. The
remaining nodes can then be formed into color classes of order four by
including three nodes of one K3 in each class. This yields a coloring with
colors. Since there are at most four nodes in any color class, this is a minimum
coloring.
Now suppose m < s. Then we can use each of the m copies of K3
together with a node in S to form m color classes of order four. We partition
the remaining s m nodes into as many 3-node classes as possible. Thus we
24


have m + f2-^] = color classes.

A theorem corresponding to Theorem 3.2.5 when j = 5 appears to
be quite complicated. For the proof of our main result in this section, we only
need to know the value of the -iC'5-chromatic number when G is missing a
single copy of K3.
Theorem 3.2.6 If {E(G)) = Kz, then x{G, ->C5) = [(n l)/4].
Proof. Let the nodes of the K3 in (E(G)) be denoted u, u, and w. Let V
be -i(75-colored with k colors and suppose A is a color class with at least five
nodes. Let B C A with \B\ = 5. If B contains no two nodes of {u, v, w}, then B
induces a complete graph and hence contains a 5-cycle. Suppose u,v B and
w 0 B. Then B = K$ e and clearly B contains a 5-cycle. If u,v,w (E B, then
it is easy to see that B is not Hamiltonian. Thus every color class must contain
at most four nodes with the exception of one class; and this class contains five
nodes only if it contains all three of the nodes u, v, and w. Thus n > A(k1)+5
from which it follows that x(G, -C's) < k < [(n l)/4]. Clearly V can be
colored by assigning one color to u,v,w and two other nodes and assigning
colors to the remaining n 5 nodes so that no color class contains more than
four nodes; that is, V can be ->Cs-colored with 1 + [(n 5)/4] = ["(rc l)/4]
colors. We have shown that = Kn ~ 1)/4"|. D
For the proof of Theorem 3.2.8, we also need to find the value of the
conditional chromatic number when G is missing a copy of P4, the path on
four nodes and when G is missing K\,2 + K2.
Theorem 3.2.7 If {E(G)) = P4 or (E(G)) = I<75) =
\n/4].
Proof. Suppose that V is -iCs-colored and let B be a subset of order five
25


contained in a color class. Even if all four of the nodes of the missing P4 or
if all five nodes of the missing K\t2 + K2 are contained in B, still B will be
Hamiltonian. (If (E(G)) = P4, let the nodes of the P4 in (E(G)) be x,y,z,w
and let u be the remaining node of B\ then y,u,z,x,w,y is a 5-cycle. If
(E(G)) = K\t2 + K2, let v be adjacent to u and w in the Ki# and let x and
y be the nodes of the K2. Then u,y,v,x,w,u is a 5-cycle.) Thus each color
class can contain at most four nodes, and it follows from Theorem 2.1.1(c) that
x(G, 'Cs) = fn/41.
Theorem 3.2.8 lfe(G) = 2), then x(G, ->Cj) = HU -1)1 for all
j > 3, except when (E(G)) = Ki,j-2 or when j = 5 and (E(G)) = K3.
In the exceptional cases, = K71 l)/(j 1)1-
Proof. If j = 3, then G is missing one edge, (E{G)) = K2, and the result
follows from Theorem 3.2.3. If j = 4, then G is missing at two edges; so
{E(G)) is either K\t2 or 2K2, and the result follows from Theorem 3.2.2 and
Theorem 3.2.3. If j = 5, the graph is missing three edges and {E(G))
{K3, Kip, SK2, P4, Kip + K2}. The result follows from Theorems 3.2.6, 3.2.2,
3.2.3, and 3.2.7.
So we may assume j > 6. If {E(G)) = the result follows from
Theorem 3.2.2. Thus we assume that (E(G)) ^ Ki,j-2- Let V be -iCj-colored
and let A be a color class. Let B C A with \B\ = j. We will show that
for every pair of nonadjacent nodes u and v in B, either u and v belong to a
Hamiltonian cycle of B or that degs(u) + degg(v) = j. It will then follow from
Theorem 3.1.1, that B is Hamiltonian and hence that A contains a j-cycle, a
contradiction. From this it follows that no color class may contain more than
j 1 nodes and hence x{G,~ 26


First we suppose that at most j 3 of the missing edges are incident
to at least one of u and v. Assume degB(u) = j 1 s for some s > 0;
that is, \H(u) fl B\ = s. There are at most j 3 edges missing at u and
v, of which s, counting the edge uv, are missing at v. So there are at most
j 3 (s 1) edges missing at v. Thus degB(v) >j 1 (j s 2) = s + l.
Now degB{u) + degB(v) > j.
This leaves the case where all j 2 missing edges are incident to at
least one of u and v. Let H = H(u, v) fl B. Since uv is a missing edge, there
are at most j 3 nodes in H. Note first that if \H\ < j 5, then there are at
least three nodes x, y, z in B H. Then since B {, v, y] is complete, there
is a Hamiltonian (x,z)-path P in B {it,v,y} and P together with the path
x, u, y, v, z is a Hamiltonian cycle in B. So it is left to consider the cases where
\H\ = j 4 or j 3. Suppose \H\ = j 4 > 2. Then there are two nodes x
and y in B H. Also since |H(u) fl H(v)\ < 1, there is at least one additional
node z adjacent to one of u or v, say u. Now the path z, u, x,v,y together
with a Hamiltonian (z, j/)-path in the complete graph B {u, v, x} forms a
Hamiltonian cycle in B. This finishes up the situation where \H\ = j 4. We
have left to handle \H\ = j 3 > 3. Here there is only one node x in B H.
However, since one of the j 2 missing edges is uv, each node of H is non-
adjacent to exactly one of u or v and adjacent to the other. Moreover, since
we assumed (E(G)) ^ Aij_2, there is at least one node y of H incident to u
and at least one z incident to v. Then z, u, x, v, y together with a Hamiltonian
(y, z)-path in the complete graph B {it, v, x} is a Hamiltonian cycle in B.
Combining Theorem 3.2.1 and Theorem 3.2.8, we get our main result.
Theorem 3.2.9 Ife(G) > () (j-2), then = \n/(j -1)1 for
27


j > 3, except when (E{G)) = K\,j-2 or when j = 5 and (E{G)) = T^.
7w the exceptional cases, x(C,~>Cj) = [(n l)/(i 1)].
3.3 Future Directions
This section addresses the future direction of conditional chromatic
number research both in terms of a general conditional property, and the spe-
cific property ~>Cj.
The value of y(G, -iCj) can be calculated using the above results for
graphs of order 4, 5, and 6 [7]. As the order of the graphs increase, this cal-
culation becomes extremely difficult due to the number of configurations of
the missing edges of G. It is possible that a generalization for the value of
x(G, -'Cj) exists, but without information about the smaller cases, this gener-
alization may be difficult to obtain. Based our experience with this problem,
we conjecture that there is no characterization for the value of x(G, ->Cj) for
all graphs. It is possible that characterizations of x{G\~'Cj) exist for specific
families of graphs, which may be easy to find. We also suspect that the proof
techniques used in Chapter 3 could be adapted to study the value of x(C, P)
with respect to other conditional properties.
Aside from this, there are several other remaining questions about the
value of x(G, -'Cj) for specific graphs. For example, the dual of the Tutte graph
mentioned in the previous chapter could lead to some interesting possibilities.
We know it provides an example of a graph that is planar with x{G,Pa) = 3,
but what is the value of x(G, -'Cj) for this graph? Is x{C, ~>Cj) = 3 for every
value of j with respect to this particular graph? Why? The result stated in
Chapter 2 only gives a bound for x(C, Cj) with this graph.
Another question is whether or not the bounds of Sampathkumar and
28


Venkatachalam are useful for x(G, ~'Cj). Do there exist graphs or families of
graphs for which these bounds are tight? If so, are they all trees because this
is the case where x(G, ~'Cj) = x(G, -'Pa) for every value of j?
Many questions also remain concerning extremal results for x(G, ~'Cj).
Is there a characterization of families of graphs that are vertex critical for cer-
tain value(s) of j? If this type of characterization is difficult (we conjecture it
is!), then what about other properties?
In Hararys 1985 paper is a list of nine conditional properties that
have been studied in some manner. He also lists other types of related
research such as conditional connectivity, extremal graph theory, chromatic
polynomials, and interpolation. It would be interesting to see a sequel that
addresses the current state of conditional chromatic research and the large
number of discoveries that have been made in only eight years.
29


REFERENCES
[1] M.O. Albertson, R. Jamison, S. Hedetniemi, and S. Lock. The subchro-
matic number of a graph. Discrete Mathematics, 74:33-49, 1989.
[2] J. Andrews and M. Jacobson. On a generalization of chromatic number.
Congr. Numer., 47:33-48, 1985.
[3] J. Andrews and M. Jacobson. On a generalization of chromatic number
and two kinds of ramsey numbers. Ars Combin., 23:97-102, 1987.
[4] P. Baldi. On a generalized family of colorings. Graphs and Combina-
torics, 6:95-110, 1990.
[5] J. Brown and D. Corneil. On generalized graph colorings. J. of Graph
Theory, ll(l):87-99, 1987.
[6] J. Brown and D. Corneil. On generalized graph colorings. Quacstiones
Mathematicae, 15:447-487, 1992.
[7] K. Casey and K. Fraughnaugh. Conditional chromatic numbers with for-
bidden cycles. To appear in Linear Algebra and Applications.
[8] G. Chartrand, D.P. Geller, and S. Hedetniemi. A generalization of the
chromatic number. Proc. Camb. Phi. Soc., 64(2):265-271, 1968.
[9] G. Chartrand and H. Kronk. The point-arboricity of planar graphs.
J.London Math. Soc., 44(4):612-616, 1969.
[10] G. Chartrand, H. Kronk, and C. Wall. The point-arboricity of a graph.
Israel J. Math., 6:169-175, 1968.
[11] G. S. Domke, R. Laskar, S.T. Hedetniemi, and K. Peters. The partite-
chromatic number of a graph. Congr. Numer., 53:235-246, 1986.
[12] F. Harary. Conditional colorability in graphs. Appears in Graphs and
Applications: Proceedings of the First Colorado Symposium on
Graph Theory John Wiley and Sons Inc., New York, 1985.
[13] F. Harary. Graph Theory. Addison-Wesley, Massachusetts, 1969.


[14] F. Harary and K. Fraughnaugh (Jones). Conditional colorablity ii: bipar-
tite variations. Congr. Numer., 50:205-218, 1985.
[15] F. Harary and K. Fraughnaugh (Jones). Degree conditional bipartition
numbers in graphs. Congr. Numer., 55:39-50, 1986.
[16] F. Harary and P. Kainen. On triangular colorings of a planar graph. Bull.
Calcutta Math. Soc., 69:393-395, 1977.
[17] S. Hedetniemi. On partitioning planar graphs. Canad. Math. Bull.,
11(2):203211, 1968.
[18] F. Kramer and H. Kramer. Ein farbungsproblem der knotenpunkte eines
graphen bezuglich der distanz p. Revue Roumaine de Mathema-
tiques Pures et Appliquees, 14(2): 1031-1038, 1969.
[19] L. Lesniak-Foster and J. Straight. The cochromatic number of a graph.
Ars Combin., 3:39-45, 1977.
[20] D.R. Lick and A.R. White, k-degenerate graphs. Cand. J. Math.,
22(5):10821096, 1970.
[21] C. Mynhardt and I. Broere. Generalized colorings of graphs. Appears in
Graph Theory with Applications to Algorithms and Computer
Science. Wiley Interscience, New York, 1985.
[22] 0. Ore. Arc coverings of graphs. Ann. Mat. Pura Appl., 55:315-322,
1961.
[23] F. Roberts. Discrete Mathematical Models. Prentice-Hall, New Jer-
sey, 1976.
[24] H. Sachs and M. Schauble. Konstruction von graphen mit gewissen
farbungseigenschafte. Beitrage zur Graphentheorie (Kolloquium,
Maneback), pages 131-136, 1968.
[25] E. Sampathkumar. Generalizations of independence and chromatic num-
bers of a graph. Discrete Math., 115:245-251, 1993.
[26] E. Sampathkumar and C.V. Venkatachalam. Chromatic partitions of a
graph. Discrete Math., 74:227-239, 1989.
31


Full Text

PAGE 1

THE CONDITIONAL CHROMATIC NUMBER OF A GRAPH by Karen Lee Casey B. S., Metropolitan State College of Denver, 1990 A thesis submitted to the Faculty of the Graduate School of the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Applied Mathematics 1993

PAGE 2

Casey, Karen Lee (M.S., Applied Mathematics) The Conditional Chromatic Number of a Graph Thesis directed by Professor Kathryn Fraughnaugh ABSTRACT The conditional chromatic number of a graph is the assignment of colors 1 ... k to the nodes such that each color class v; ... Vk induces a sub graph with property P. The conditional chromatic number with respect to the property that a graph have no cycle for a fixed j is studied, and a survey of known results is given. New results for this property are given when the number of edges in a graph is large. This abstract accurately represents the content of the 'Candidate's thesis. I recommend its publication. Signed ll1

PAGE 3

This thesis for the Master of Science degree by Karen Lee Casey has been approved for the Department of Mathematics by David C. Fisher Date 1 I

PAGE 4

DEDICATION To Sean Dargen the Systems Administrator of DARGENET for all of your technical and emotional support.

PAGE 5

ACKNOWLEDGEMENTS I would like thank Dr. Kathryn Fraughnaugh for the time and energy she spent assisting me in this endeavor for which I am very grateful. Addi tionally, I would like to thank Dr. David Fisher, and Dr. Rich Lundgren for their guidance and support. Finally, I would like to say THANK YOU to all of my friends for your encouragement and support during the last year and a half! v

PAGE 6

CONTENTS CHAPTER 1 INTRODUCTION 1.1 Definitions and Notation 1.2 History . . . . 2 PRELIMINARY RESULTS 2.1 Seven Properties of x( G, -,C;) 2.2 Implications for x(G, -,C;) from x(G,Pa) 2.3 General Results for -,C; 3 NEW RESULTS . 3.1 Ore's Theorem 3.2 The Value of x(G, -,C;) When IE( G) I Is Large 3.3 Future Directions References 2 3 6 9 9 11 18 20 20 21 28 30

PAGE 7

CHAPTER 1 INTRODUCTION The chromatic number of a graph G, is defined to be the smallest number of colors needed to color G, such that no two adjacent vertices have the same color (13]. Analogously, the chromatic number can be defined as the minimum n, for which there exists an n-partition of the vertices, such that each induced subgraph contains no complete graph on two vertices. Each set of the partition of the vertices is called a color class. The chromatic number can be generalized in several different ways. For example, the nodes of a graph can be colored such that the subgraphs of G formed from the color classes contain no path on a fixed number of vertices. Another generalization is to color the nodes of G such that the subgraphs contain no cycles. In fact, any graph theoretical property can be used to generalize the chromatic number. The generalized chromatic number is defined as the minimum number of colors needed to color the nodes of G such that every subgraph of G induced by a color class has property P (various authors, see [1]). This generalization to any property is now referred to as the conditional chromatic number of a graph [12]. In the following sections we will discuss the history of the conditional chromatic number, relate known results to the property of containing no cycles, and prove new results for the value of the conditional chromatic number with respect to the property of forbidding cycles of a fixed length.

PAGE 8

1.1 Definitions and Notation The graphical definitions and notation of (13] will be used, except that a graph G = (V,E) will refer to vertex set V, with lVI = n = n(G), and edge set E, with JEI = e = e(G) in addition to nodes and lines. Every graph G will be simple without loops. A cycle (or j-cycle) Cj is a simple cycle on j 2': 3 nodes. Define a graph G to be planar if it can be embedded in a plane S such that when it is drawn on S no two edges intersect. A graph G is outerplanar if it can be embedded in the plane so that all its vertices lie on the same face. Let mG denote m disjoint copies of the graph G. The minimum vertex degree and the maximum vertex degree will be denoted ii( G) and L':.( G) respectively. A cycle is Hamiltonian if it has no repeated vertices and contains all of the vertices of G. A graph is Hamiltonian if it contains a Hamiltonian cycle (23]. For X<;;; V, define N(X) = {ujuv E E for some vEX}, N(X] = N(X) U {X}, and H(X) = V -N[X]. When X is a single vertex x, the preceding definitions correspond respectively to the usual definitions of the open neighborhood of x, closed neighborhood of x, and non-neighbors of x. Define the girth g( G) to be the length of the shortest cycle in G. The chromatic number of a graph G is the smallest integer, x(G), so that the vertices of G can be assigned the numbers 1, 2, ... x(G) in such a manner that each color class V;, 1 :S: i :S: x(G), induces a subgraph (V;) that consists entirely of isolated points. If Sis a subset of either E or V, then (S) is the subgraph of G induced by S. A coloring is said to be proper if no two distinct adjacent vertices have the same color. As an example, x(K5 ) = 5, because each color class can contain 3

PAGE 9

exactly one vertex (see Figure 1). If any color class contained more than one vertex, the graph induced from the color class would contain at least two vertices that are adjacent (every vertex is adjacent to every other vertex in a complete graph). s 2 4 3 Figure 1. Labeling the vertices as shown above, we can partition the vertices as Vi= {1}, v2 = {2}, Va = {3},\14 = {4} and Vi;= {5}. Each graph induced by V;, 1 :::; i :::; 3, contains no K2 If any partition contained more than one vertex, the induced graph would contain a K2. Therefore, x(G) = 5. The conditional chromatic number with respect to a graph theoretical property P, denoted x(G,P), is the minimum n for which there exists annpartition, V = UV; such that for each i, the induced graph (V;) is in P. If P is the property that the subgraph induced from each color class be cycle free, we will denote the conditonal chromatic number as x( G, P.). This number is also referred to as the point arboricity of a graph. If P is the property that a given graph F be forbidden to be induced by any subset of the vertices in V;, the conditional chromatic number is denoted as x( G, -.F). For the remainder of this paper x( G, -.F) will also be'referred to as a -.F -coloring, -.F -chromatic number, and F-Free chromatic number. In any case where P is ambiguous, we will let denote the property of forbidding 4

PAGE 10

the subgraph F. The property of forbidding cycles of a fixed length, denoted x( G, ), will be studied in the remainder of the paper. Define a graph G to be vertex P k-critical if and only if x(G, P) = k, but x(G v, P) < k for all v E V(G). As an example of let G = I<5 the complete graph on five vertices shown in Figure 1. The conditional chromatic number of ](5 with respect to the property of forbidding cycles, yields the following values of x( G, ), for differing values of j. If j = 3, then x(G, = 3, because each color class can consist of no more than two vertices (if a class contained three vertices the corresponding graph would induce a K3 because G is complete). With a maximum of two vertices in each color class, we need to partition the vertices of G into three classes (two classes consisting of two vertices, and one class consisting of one vertex). If j = 4, then x(G, = 2, because each color class can consist of no more than three vertices (same reasoning as above). We partition the vertices into two color classes, one consisting of three vertices, and the other consisting of the remaining two vertices of G. If j = 5, then x(G, = 2, because each color class can consist of no more than four vertices (same reasoning as above). We partition the vertices into two color classes one of two ways shown in Figure 1: one color class can consist of three vertices and the other color class can consist of the remaining two vertices, or one color class can consist of four vertices and the other color class can consist of the remaining vertex. Labeling the vertices as in Figure 1, the vertices can be partitioned as Vi = {1,2,3}, \12 = {4,5} or 5

PAGE 11

V1 = { 1, 2, 3, 4}, Y2 = { 5}. The graph induced by Vi, 1 :S i :S 2, contains no Cs. If j = 6, then x(G, = 1, because each color class can consist of five vertices without containing a C6 In Chapter 2 we will prove that if the size, j, of the cycle being forbidden is larger than the number of vertices of G, x(G, = 1. 1.2 History The first published articles about conditional chromatic numbers ap peared in 1968 in [8], [17], [10], and [9]. The definitions and notation used in these papers was not consistent, so it will be clarified when necessary, and re stated using the notation of [12]. The following is an overview of these papers, emphasizing results related to the conditional property of forbidding cycles of a fixed length. In [8] the conditional chromatic number is studied with respect to the property that each induced subgraph contain no path of a fixed length. The authors denoted this number as Xn (G). Using the contemporary notation, these numbers would be denoted x(G, for j fixed. The authors showed that for every positive value of j, there exists a planar graph G such that x( G, = 4. This proves that no result stronger than a "Four Colour Theorem" is possible (see paper for details). As another example, in [17] Hedetniemi defined a P-set of G to be a subset of the vertices of G such that the subgraph induced by S property P. He also defined a P-coloring of a graph to be, an assignment of colors to the vertices of G, such that for any given color the set of vertices having this color is a P-set. The definition of a P-set is equivalent to that of a color class 6

PAGE 12

inducing a subgraph having property P. A ?-coloring is equivalent to a proper coloring with respect to property P. Hedetniemi found an upper bound for the value of the chromatic number with respect to the property that each color class be cycle free. This property is also called the point arboricity of a graph, and as we defined in the previous section, is denoted x( G, Pa) Hedetniemi's results are strengthened in [1 0] and [9] and will be used below to determine bounds for x( G, -.Cj ). Another example of a property that has been studied, is the prop erty P that each V; contain no complete graph on three vertices, denoted x(G, -.K3 ) = x(G, -.C3). The authors in [16] present a conjecture for the value of x(G, -.1{3), when G is a planar graph, and prove a result about x(G, -.1{3 ) when G is a maximal planar graph. In a sense, this paper bridged the gap between the 1968 results, and the 1985 re-emergence of conditional chromatic research. In the paper titled "Conditional Colorability in Graphs", Harary [12] provided notational clarification, standardization, as well as a comprehensive survey of nine known results for generalized chromatic numbers. Harary used these new definitions to write the standard chromatic number of a graph as x(G, -.K2). Harary's definitions and notational standard are used throughout the remainder of this paper (see previous section). More recent terms referring to the conditional chromatic number of a graph include: the general chromatic number [26], the Pk-chromatic number [6], the P chromatic number [1], the Ffree chromatic number [21], a -.G kcoloring [5], and a generalized family of colorings [4]. For a survey of conditional colorability research, see [12] and [1]. The table below summarizes some of 7

PAGE 13

the conditional properties that have been studied, and their corresponding references. A Table of Conditional Properties I Color Class Property I Reference disconnected or trivial Hedetniemi (1968) [17] acyclic Hedetniemi (1968) [17] contains no Pj for fixed j Chartrand, Geller, Hedetniemi (1968) [8] contains no K, for fixed j Sachs, Schauble (1968) [24] minimum vertex degree 2: j Kramer, Kramer (1969) [18] for fixed j Lick, White (1970) [20] contains no K3 Harary, Kainen (1977) [16] complete or empty LesniakFoster, Straight (1977) [19] contains no ( u, v) with Neeralagi, Venkatachalam (1977) [1] distance( u, v) = j maximum vertex degree ::; j Harary, Fraughnaugh (1985) [14], [15] Andrews, Jacobson (1985) [2], [3] disjoint union of Domke, Laskar, complete subgraphs Hedetniemi, Peters (1986) [11] contains no ( u, v) with Baldi (1990) [4] distance ( u, v) ::; j j independent for fixed j Sampathkumar (1993) [25] has no cycles for fixed j Casey, Fraughnaugh (1993) [7] 8

PAGE 14

CHAPTER 2 PRELIMINARY RESULTS This chapter begins the study of the conditional chromatic number with respect to property, P = -.Cj, for a fixed j 2 3. The first theorem states seven basic properties of x( G, -.Cj) that follow from definitions. These properties will be used throughout the remainder of the paper. In the second section of this chapter, established conditional chromatic number results for point arboricity are used to prove bounds for the value of x( G, -.Cj ). In the third section, general conditional chromatic number results for properties that are hereditary are restated specifically for x( G, -.Cj ). 2.1 Seven Properties of x(G, -.Cj) Although all of the properties in this theorem are straightforward, they will be important to the establishment of new results in Chapter 3. Note that properties (b), (d), (f), and (g) follow from observations of previous au thors [12]. THEOREM 2.1.1 (a) xU
PAGE 15

(e) x( G, -.Cj) = 1 if and only if G contains no Cj. Consequently, for n < j, x(G, -.Ci) = 1. (f) x(G, -.Ci) :.S x(G, Pa) :.S x(G). (g) For the complete bipartite graph G = I 2p if j is even and 4 :.:; j :.:; 2p Proof. (a) A proper coloring of I
PAGE 16

(d) Each G; is a subgraph of G so by (2) above maxi{x(G;, x(G, We now must show maxi{x( G;, 2': x( G, ). Assume max;{x(G;, = k. Then every other component of G can be prop erly colored with :::; k colors. Since all components are disconnected from each other, the vertices from each non-maximal component can be in cluded in the k color classes of the maximal component without creating a Cj. Then the number of colors needed to color G is no more than k = (e) x(G, = 1 <* every vertex of G can be colored the same color <* G contains no Cj If n < j then G can not contain a Cj. Following the argument backwards implies x( G, = 1. (f) It follows from the definitions of x( G) and x( G, Fa) that a coloring that satisfies the former, will satisfy the latter, and a coloring that satisfies the latter will not necessarily satisfy the former, therefore x(G, Fa) :::; x(G). Similarly, x(G, x(G,Fa). (g) If G is the complete bipartite graph, then G contains no odd cycles but contains even cycles of every length j for j up to and including 2p. The graph can be colored with two colors by assigning a color to each of the two sets of the bipartition. 0 2.2 Implications for x(G, from x(G, Fa) In 1968 Hedetniemi [17], Chartrand and Kronk [9], and Wall [10], studied the conditional property Fa that each color class have no The Fa-chromatic number is also called the point arboricity. From Theorem 2.1.1() it follows that an upper bound on the point arboricity for a family of graphs is 11

PAGE 17

also an upper bound for the -,Cj-chromatic numbers for the given family and each value of j 2: 3. This section examines the major results of Fa -chromatic numbers and translates them into -,Ci-chromatic number results. The Fa-chromatic number results of this section are divided into three parts, the first examines upper bounds for the Fa-chromatic number, the second improves these results if G is planar (or outerplanar), and the third consists of more recent Fa-chromatic number results. The study of Fa-chromatic numbers began with a series of papers in 1968 in which the authors proved upper bounds for x(G, Fa) All of the results below that are attributed to [10] and [9] can be similarly attributed to [17]. Chartrand, Kronk and Wall [10] interpreted the point arboricity (Fa) of a graph as a "coloring number" since Fa(G) is the minimum number of colors needed to color the vertices of G such that no cycle has all of its vertices colored the same. Using an inductive argument on the number of vertices of a graph they proved the following theorem. THEOREM 2.2.1 For any graph G, For complete graphs Theorem 2.2.1 is tight because the maximum number of vertices in any color class is two any more and the graph induced by the vertices of the color class consists of a cycle of length three. Therefore, On the other hand, for planar graphs with large maximum degree this bound is not very strong. For example the complete bipartite graph K1 ,10 is planar with 6(G) = 10, so from Theorem 2.2.1 x(G,Fa) ::0 = 6. But 12

PAGE 18

K1 ,10 contains no cycles so x(G, Pa) = 1. As we will see below this bound can be improved for planar graphs! In 1969 Chartrand and Kronk [9] established an upper bound similar to that given in Theorem 2.2.1 above. The two main theorems of [9], and a brief justification of each are stated below. THEOREM 2.2.2 For any graph G, rt..(G)l x(G,Pa) 1 + -2 -. The proof of Theorem 2.2.2 relies on the fact that there exists an in duced n-critical (see section 1.2) subgraph H of G. Additionally, the minimum vertex degree of H is less than or equal to the maximum over all minimum degrees of subgraphs of H. Using the n-critical property the result follows, see [9] Theorem 1 for details. Note that Theorem 2.2.1 and 2.2.2 produce the same bound when t..(G) is even, but when t..(G) is odd the bound in Theorem 2.2.2 is smaller. The next theorem improves the upper bound for x(G, Pa) in the case that G is non-regular, i.e., every vertex is not of the same degree. THEOREM 2.2.3 If G is a connected and non-regular graph, then Theorem 2.2.1 and 2.2.3 immediately give the following upper bounds for the numbers. THEOREM 2.2.4 For all j :2: 3 and for all graphs G, ( G C)< rl +.t..(G)l X J -2 If in addition G is non-regular and connected, then ( G C) < ll+ t..(G)J X J -2 13

PAGE 19

Note that in the previous two theorems we must assume G is a con nected graph otherwise the graph in Figure 2 would be a counterexample. Figure 2. This graph consists of disconnected components K3 and K2 From Theorem 2.2.4 x(G,-.C3) = 1, but clearly x(G,-.C3) = 2 because one of the disconnected components of G is C3. Although the complete graphs demonstrate that the inequality in Theorem 2.2.4 is best possible for P., the complete graphs only demonstrate that it is best possible for when j = 3. For example, consider x(G, -.C4 ) with G = K5 From Theorem 2.2.4 x(G,-.C4) r1t4l = 3. This bound is not tight because x( G, -.C4 ) = 2 (see the discussion at the end of Chapter 1, Section 2). We do not yet know a family of graphs for which the bound is tight when j :?: 4. It is possible that no such family exists. It is easy to conjecture that Theorem 2.2.1 can be improved for planar graphs because x(G,P.) x(G), see 2.1.1 (f), and from the Four Color Theorem, see [10], x( G, P.) 4. In fact, x(G, P.) 3 for planar graphs, which was proved in [10],[9] and [17]. THEOREM 2.2.5 For every planar graph x(G, P.) 3. 14

PAGE 20

To prove Theorem 2.2.5, Chartrand and Kronk observed that every induced sub graph of a planar graph is planar, and that every planar graph contains at least one point of degree 4 or less. From Theorem 2.2.2 x( G, P.) ::; 1 + r 1 and the result follows. Chartrand and Kronk used the dual of the Tutte graph as an example to show equality for Theorem 2.2.5. \<,, 1(2.. (\_ "' \o Figure 3 -The Tutte Graph. The dual of this graph has point arboricity three. Figure 3 is a Tutte graph, a planar graph whose dual G* has point arboricity 3. The dual of a graph G can be constructed as follows: each region (labeled R1 .... Rk) of G is represented by a vertex in G*, and an edge exists between two vertices in G* if and only if the corresponding regions of G are adjacent. The proof that G* has point arboricity three is as follows. 15

PAGE 21

We will show it takes exactly three colors, to color the regions of G (and thus vertices of G*). Assume we can color G with two colors, and label the regions of G as shown in Figure 3. No three of R1,R2 and R3 can be colored the same color without inducing a C3 So color two of Rl> R2 R3 with color a and color the remaining region b. The region, R4 outside G is adjacent to R1 R2 and R3 If R4 were colored with color a, then G* would contain a C3 so it must be colored with color b. Assume BWOC that R5 is adjacent to the two large regions colored with color a. It follows that R5 must be colored with color b, otherwise, G* would contain a C3 Similarly, at least one of R,; or R7 would have to be colored with color b. Assume R7 is colored b, this forces R,; to be colored a. Then R8 cannot be a, so color it b. Since both R8 and R4 are colored b, this forces R9 to be a, and thus R10 to be b. If R11 is colored a then together with R1 R2 R,;, and Rg they form a C5 in G*. Otherwise, if R11 is colored b, then together with R7 and R9 they form a C3 in G*. So R11 must be colored with a third color. Similar reasoning is used for the case of R5 adjacent to R1 colored a and R2 colored b. Because the graph is symmetric, these two cases yield the minimal number of colors needed color G*, which is three. Figure 3 shows G colored with three colors. Another class of graphs studied in [17] and [9] is the subclass of planar graphs known as outerplanar graphs. Any planar graph is also outerplanar if it can be embedded in a plane such that all of its vertices lie on the exterior 16

PAGE 22

region. It can be shown that if a graph is outerplanar then x(G) :S 3, see [17]. Additionally, every outerplanar graph contains at least one vertex of degree less than or equal to two, see [13]. These two observations, along with an inductive argument proves the following theorem. THEOREM 2.2.6 lfG is outerplanar, then x(G,Pa) :S 2. The following implications for x(G, -,Cj) are immediate from the above results. THEOREM 2.2.7 (a) If G is a planar graph, then x( G, """'Cj) :S 3 for all j 2: 3. (b) IfG is an outerplanar graph, then x(G, """'Cj) :S 2 for all j 2: 3. As a final note, the first two parts of the following theorem are from Sampathkumar and Venkatachalam [26] and are upper and lower bounds for the point arboricity and thus a bound for x( G, """'Cj ). These results may lead to a future direction and are stated here for completeness. THEOREM 2.2.8 (a) For every graph G, Vn :S x(G, Pa) + x(G, Pa) :S Hn + 3). (b) For every graph G, :S x(G, Pa)x(G, Fa) :S + 3)]2 THEOREM 2.2.9 (a) For every graph G, x(G, 'Ci) + x(G, -.Cj) :S !(n + 3). (b) For every graph G, x(G, """'Cj)x(G, -.Cj) :S [l(n + 3)]2 The upper bound given in Theorem 2.2.9 (a) above is tight for G = Kn when n is odd and j = 3. We can prove this as follows: From Theorem 2.1.1 (a) x(Kn,"""'Cj) = = Since n is odd, = Since G is complete, G is completely disconnected thus x(G, -,C3 ) = x(I
PAGE 23

+1 = We have been unable to find a family of graphs for which the upper bound in Theorem 2.2.9 (b) is tight and conjecture this bound can be improved upon. 2.3 General Results for -,C; This section relates more recent results about conditional chromatic numbers. In the paper "On Generalized Graph Colorings" by Brown and Corneil [6], several general results are proved about the conditional chromatic number of a graph, given the property P under investigation is hereditary. A property is hereditary if and only if when a graph G has P, then any subgraph H of G has P. The property of forbidding cycles of a fixed length j is hereditary because if a graph does not contain a cycle for a fixed value of j, then none of its subgraphs contain a cycle for a fixed value of j. Therefore, each of the results in [6] holds true for x( G, -,C; ). Following the results of Mynhardt and Broere [21], Brown and Corneil [6] investigated the existence of graphs with arbitrarily high P-conditional chromatic number. All of the Brown and Corneil results summarized in this section assume P is non-trivial and hereditary. THEOREM 2.3.1 (a) If P is non-trivial (G # P), and hereditary then there exists a graph G with x(G, P) = k for all k 2 1. (b) Every P -conditional chromatic graph contains a vertex P k-crjtical sub graph. (c) Any P-conditional chromatic graph contains a vertex P -critical subgmph for all C < x(G,P). 18

PAGE 24

I I I I I I I A proof for part (a) was originally proved by Folkman in 1970. An-other proof was given using Ramsey theory for hypergraphs in a Brown and Corneil manuscript. A somewhat less complicated proof of (a) appears in [6]. Part (b) is proved using the definition of vertex critical and the properties of vertex critical graphs. Brown and Corneil proved part (c) using an induction argument, on the critical vertex. Another question addressed in [6] concerns the number of ways the vertices of G can be uniquely colored. Unique colorings exclude permutations of either the vertices or the colors. Although these results are applicable to the general theory of conditional chromatic numbers, they are not applicable to the specific conditional chromatic number with respect to forbidding cycles of a fixed length and will be omitted. Additionally, Sampathkumar [25] extended the Brown and Corneil results with respect to the chromatic number of critical graphs. At this time, analogous results do not exist for conditional chromatic numbers of critical graphs. 19

PAGE 25

I I I I I I I I I I I I CHAPTER 3 NEW RESULTS In this chapter a result of Ore's together with the results established in the preceding chapter provide a basis for determining the value of x( G, -,Cj) when G has a large number of edges. 3.1 Ore's Theorem Following are two standard results of Ore's [22] about Hamiltonian graphs, which are necessary for the next section. THEOREM 3.1.1 In a graph G with n 2: 3, if for every pair u and v of nonad jacent vertices deg( u) + deg( v) 2: n, then G is Hamiltonian. THEOREM 3.1.2 If G is a graph with n 2: 3 and IE( G) I 2: (n2 -3n + 6)/2, then G is Hamiltonian. Proof. Assume IE(G)I 2: (n2 -3n + 6)/2. Since every graph on n nodes is either a complete graph, or subgraph of a complete graph, the maximum number of edges G is missing can be computed by subtracting (n2 -3n + 6)/2 from 1) (the number of edges in Kn) The result of this computation is n-3. So there are at most n 3 edges missing from G. Assume BWOC there exists (u,v) a pair of non adjacent vertices in G such that deg( u) + deg( v) < n. This implies the total number of edges missing from G is at least n -1 a contradiction. Therefore, from Ore's Theorem above, G is Hamiltonian.

PAGE 26

3.2 The Value of x(G,-,Cj) When IE(G)I Is Large In this section we investigate the value of x( G, ...,C;) when the number of edges in G is large [7]. Now we present a series of theorems in which the value of x( G, ...,C;) is given when G is missing a small number of edges. First we find the value of the conditional chromatic number when G is missing j 3 or fewer edges. THEOREM3.2.1 lfe(G):?:(;) (j-3),thenx(G,...,Cj)=fnj(j-1)lforall j:::: 3. Proof. From Theorem 2.1.1(c), it follows that x(G, -,C;):::; fn/(j -1)l Sup pose by way of contradiction that G is -,Cj-colored with fewer than fn/(j -1)1 colors. Then some color class A contains at least j nodes. Let B A with lEI = j. Then e(B) :2: j(j-1)/2-(j-3) = (j2 -3j + 6)/2. It follows from Theorem 3.1.2 that B is Hamiltonian. Therefore A contains a j-cycle, a contradiction. Thus x(G, ...,C;) = fn/(j -1)1. D Next we want to find the values of x(G, ...,C;) when G is missing j -2 edges. On the way to this result, we show that when the complement of G contains edges that induce particular types of subgraphs, the values are readily found. THEOREM 3.2.2 If G is a graph for which (E(G)) = I<1,m for j-2 :::; m :::; n -1, then x(G,...,Ci) = f(n -1)/(j -1)1 for all j :2:3. Proof. Let v be the node of degree min the subgraph of (E(G)) induced by the I<1,m Let A be a color class in a -,Ci-coloring of G with k colors. If v is not in A, then A induces a complete subgraph of G and hence contains an IAI-cycle. Thus, every color class not containing v has at most j-1 elements. If v E A and IAI :2: j + 1, then A-{ v} induces a complete graph on j nodes and 21

PAGE 27

hence contains a j -cycle. Thus the color class containing v contains at most j elements. Since there are k-1 color classes with at most j -1 elements and one color class with at most j elements, n ::; ( k-1 )(j -1) + j = k(j-1) + 1. Thus x(G, "'C;) :2: k :2: l(n1)/(j-1)1. On the other hand, we can color V as follows: Color v and j -2 of its non-neighbors plus one additional node with color 1. Since the degree of v in this color class is at most 1 and the class contains j nodes, clearly this class has no j-cycle. Color the remaining n-j nodes so that no color class contains more than j -1 nodes. This gives a "'C;-coloring of V with 1 + l(nj)f(j-1)1 = l(n1)/(j-1)1 colors. Thus we have shown x(G, "'C;) = l(n 1)/(j-1)1. 0 THEOREM 3.2.3 If(E(G)) = mK2 where 1::; m::; ln/2J, then x(G,..,C3) = ln-;m 1 Proof. Let M = E( G) and let A be a color class in a minimum ..,C3-coloring C of G. Since any subgraph induced by five nodes is missing at most two edges of M and therefore must contain a triangle, IAI ::; 4. If lA I = 4, then in order that A be C3-free, A must be missingexactly two edges of M. Also if IAI = 3, then A must be missing exactly one edge of M. Let a be the number of color classes in C with four nodes; b, the number with three nodes; and c, the number with no more that two nodes. Then b = m -2a r for some nonnegative integer r and since C is a minimal coloring, c = ln-4;-3'1 The number of colors in C is a + b + c, so that x(G,"'C3) =a+ b+ In -4a -3b1 = ln-2abl 2 2 = 1n-2a-(;-2a-r)l = 1n ;+rl:::: 22

PAGE 28

Now we want to produce a --,C3-coloring for G with fn-;;m 1 colors. Let n = 2m + 8 for 8 2: 0 and suppose first that m is even. Form m /2 classes of four nodes, each class consisting of the endpoints of two edges of M. From the remaining nodes, form f s /21 classes with at most two nodes. This gives a coloring with colors. Now suppose m is odd. Form (m-1)/2 classes of four nodes, each class consisting of the endpoints of two edges of M. If 8 = 0, then take the remaining class to be the two endpoints of the remaining edge of M. We get + 1 = mt = f';'l = rn-;;m1 colors. If 8 2: 1, then form one additional class containing the remaining edge of M and any other of the remaining nodes and f ( s-1) /21 classes of at most two nodes. Then we have used + 1 + f ';11 = rmi'l = rn-;;m 1 colors. D The next theorem simply confirms that missing m independent edges from G does not reduce the value of x( G, --,C;) when j 2: 4. THEOREM 3.2.4 If (E(G)) = mi<2 where 1::; m::; ln/2J, then x(G, --,C;) = r j 1 1 for all j 2: 4. Proof. Let A be a set of j nodes and let v E A. Since the missing edges are in dependent, at most one of these is incident to v. Hence deg(A) ( v) 2: j -2 2: j /2 for j 2: 4. It follows from Theorem 3.1.1 that A induces a Hamiltonian sub graph, i.e., a subgraph with a j-cycle, and hence that no color class contains more than j -1 nodes. Thus x(G, --,C;) 2: fn/(j -1)1 and the equality follows from Theorem 2.1.1(c). D However, when G is missing disjoint copies of I<3 the values of the --,C;-chromatic numbers may be smaller for j 2: 4. 23

PAGE 29

I I I I I I I I THEOREM 3.2.5 If (E(G)) = mi<3 where 1 ::; m::; ln/3J and n =3m+ s, then if 0 ::; s ::; m if s > m Proof. Let A be a color class in a minimum C of G. Suppose IAI ::;:: 5. Then in the sub graph B induced by any five nodes of A, the maximum number of missing edges is four and they must occur in !(3 + K2 But even in this case B contains a 4-cycle. Thus IAI ::; 4. If IAI = 4, then in order that A be C4-free, A must be missing three edges in a single copy of /(3 Clearly, if IAI ::; 3, A contains no 4-cycle. Let a be the number of classes of order four and b the number of order three or smaller. Since each color class of order four must be missing the edges of a K3 a ::; m. In addition, since C is minimum, b = rn-;4 l so that n 4a n-a n-m 3 l=r-3-l:::::r 31Now we want to produce a minimum Let n = 3m + s for some nonnegative number s and let S be the set of nodes that are not an endpoint of an edge in a /(3 If 0 ::; s ::; m, then each of the nodes in S can be added to the three nodes in a /(3 to form a color class of order four. The remaining nodes can then be formed into r n-:;4 l color classes of order four by including three nodes of one K3 in each class. This yields a coloring with colors. Since there are at most four nodes in any color class, this is a minimum coloring. Now suppose m < s. Then we can use each of the m copies of /{3 together with a node in S to form m color classes of order four. We partition the remaining s m nodes into as many 3-node classes as possible. Thus we 24

PAGE 30

have m + r '3m 1 = r H;m 1 = rn-;m 1 color classes. D A theorem corresponding to Theorem 3.2.5 when j = 5 appears to be quite complicated. For the proof of our main result in this section, we only need to know the value of the number when G is missing a single copy of K3 THEOREM 3.2.6 If (E(G)) = K3, then x(G, = r(n -1)/41. Proof. Let the nodes of the K3 in (E(G)) be denoted u,v, and w. Let V be with k colors and suppose A is a color class with at least five nodes. Let B <;;:; A with lEI= 5. If B contains no two nodes of { u, v, w}, then B induces a complete graph and hence contains a 5-cycle. Suppose u, v E B and w '/. B. Then B = K5 -e and clearly B contains a 5-cycle. If u, v, w E B, then it is easy to see that B is not Hamiltonian. Thus every color class must contain at most four nodes with the exception of one class; and this class contains five nodes only if it contains all three of the nodes u, v, and w. Thus n 2 4( k-1) +5 from which it follows that x(G, :::; k :::; r(n-1)/4l Clearly V can be colored by assigning one color to u, v, w and two other nodes and assigning colors to the remaining n -5 nodes so that no color class contains more than four nodes; that is, V can be with 1 + r(n-5)/41 -r(n-1)/41 colors. We have shown that = r(n -1)/41. D For the proof of Theorem 3.2.8, we also need to find the value of the conditional chromatic number when G is missing a copy of P4 the path on four nodes and when G is missing K1 2 + K2 THEOREM 3.2.7 If (E(G)) = ?4 or (E(G)) = K1,2 + K2, then x(G, = rn/41. Proof. Suppose that V is and let B be a subset of order five 25

PAGE 31

contained in a color class. Even if all four of the nodes of the missing P4 or if all five nodes of the missing K1,2 + !(2 are contained in B, still B will be Hamiltonian. (If (E(G)) = P4 let the nodes of the P4 in (E(G)) be x, y, z, w and let u be the remaining node of B; then y, u, z, x, w, y is a 5-cycle. If (E(G)) = K1 2 + K2 let v be adjacent to u and win the K1 2 and let x and y be the nodes of the /{2 Then u,y,v,x,w,u is a 5-cycle.) Thus each color class can contain at most four nodes, and it follows from Theorem 2.1.1(c) that x(G,Cs) = fn/41. o THEOREM 3.2.8 If e(G) = (;)(j-2), then x(G, Cj) = fnf(j l)l for all j 2: 3, except when (E(G)) = I<1,j-2 or when j = 5 and (E(G)) = I<3. In the exceptional cases, x(G, Cj) = f(n1)/(j1)1. Proof. If j = 3, then G is missing one edge, (E(G)) = K2 and the result follows from Theorem 3.2.3. If j = 4, then G is missing at two edges; so (E(G)) is either K1,2 or 2I<2 and the result follows from Theorem 3.2.2 and Theorem 3.2.3. If j = 5, the graph is missing three edges and (E(G)) E {I<3, K1,3, 3[(2, P4, I<1,2 + I<2}. The result follows from Theorems 3.2.6, 3.2.2, 3.2.3, and 3.2.7. So we may assume j 2: 6. If (E(G)) = I<1,j_2 the result follows from Theorem 3.2.2. Thus we assume that (E(G)) =f I<1,j_2 Let V be Cj-colored and let A be a color class. Let B c;; A with IBI = j. We will show that for every pair of nonadjacent nodes u and v in B, either u and v belong to a Hamiltonian cycle of B or that degs(u) + deg8(v) = j. It will then follow from Theorem 3.1.1, that B is Hamiltonian and hence that A contains a j-cycle, a contradiction. From this it follows that no color class may contain more than j -1 nodes and hence x(G,Cj) = fnf(j 1)1. 26

PAGE 32

First we suppose that at most j-3 of the missing edges are incident to at least one of u and v. Assume degB(u) = j-1 -s for some s > 0; that is, IH( u) n Bl = s. There are at most j -3 edges missing at u and v, of which s, counting the edge uv, are missing at v. So there are at most j-3-(s -1) edges missing at v. Thus degB(v) 2 j -1-(j-s-2) = s + 1. Now degB(u) + degB(v) 2 j. This leaves the case where all j -2 missing edges are incident to at least one of u and v. Let H = H(u,v) n B. Since uv is a missing edge, there are at most j -3 nodes in H. Note first that if IHI ::; j -5, then there are at least three nodes x, y, z in B-H. Then since B-{ u, v, y} is complete, there is a Hamiltonian ( x, z )-path P in B -{ u, v, y} and P together with the path x, u, y, v, z is a Hamiltonian cycle in B. So it is left to consider the cases where IHI = j -4 or j -3. Suppose IHI = j -4 2 2. Then there are two nodes x andy in B-H. Also since IH(u) n H(v)l::; 1, there is at least one additional node z adjacent to one of u or v, say u. Now the path z, u, x, v, y together with a Hamiltonian (z,y)-path in the complete graph B-{u,v,x} forms a Hamiltonian cycle in B. This finishes up the situation where IHI = j -4. We have left to handle IHI = j -3 2 3. Here there is only one node x in B H. However, since one of the j -2 missing edges is uv, each node of H is non adjacent to exactly one of u or v and adjacent to the other. Moreover, since we assumed (E(G)) # I<1 ,1 _2 there is at least one node y of H incident to u and at least one z incident to v. Then z,u,x,v,y together with a Hamiltonian (y, z )-path in the complete graph B-{ u, v, x} is a Hamiltonian cyde in B. 0 Combining Theorem 3.2.1 and Theorem 3.2.8, we get our main result. THEOREM 3.2.9 If e(G) 2 (;)(j-2), then x(G, '""'Ci) = r nj(j -l)l for all 27

PAGE 33

j 2': 3, except when (E(G)) = I
PAGE 34

Venkatachalam are useful for x( G, Do there exist graphs or families of graphs for which these bounds are tight? If so, are they all trees because this is the case where x(G, = x(G, for every value of j? Many questions also remain concerning extremal results for x( G, Is there a characterization of families of graphs that are vertex critical for cer-tain value(s) of j? If this type of characterization is difficult (we conjecture it is!), then what about other properties? In Harary's 1985 paper is a list of nine conditional properties that have been studied in some manner. He also lists other types of "related" research such as conditional connectivity, extremal graph theory, chromatic polynomials, and interpolation. It would be interesting to see a sequel that addresses the current state of conditional chromatic research and the large number of discoveries that have been made in only eight years. 29

PAGE 35

REFERENCES [1] M.O. Albertson, R. Jamison, S. Hedetniemi, and S. Lock. The subchromatic number of a graph. Discrete Mathematics, 74:33-49, 1989. [2] J. Andrews and M. Jacobson. On a generalization of chromatic number. Congr. Numer., 47:33-48, 1985. [3] J. Andrews and M. Jacobson. On a generalization of chromatic number and two kinds of ramsey numbers. Ars Combin., 23:97-102, 1987. [4] P. Baldi. On a generalized family of colorings. Graphs and Combina torics, 6:95-110, 1990. [5] J. Brown and D. Corneil. On generalized graph colorings. J. of Graph Theory, 11(1 ):87-99, 1987. [6] J. Brown and D. Corneil. On generalized graph colorings. Quaestiones Mathematicae, 15:447-487, 1992. [7] K. Casey and K. Fraughnaugh. Conditional chromatic numbers with forbidden cycles. To appear in Linear Algebra and Applications. [8] G. Chartrand, D.P. Geller, and S. Hedetniemi. A generalization of the chromatic number. Proc. Camb. Phi. Soc., 64(2):265-271, 1968. [9] G. Chartrand and H. Kronk. The point-arboricity of planar graphs. J.London Math. Soc., 44(4):612-616, 1969. [10] G. Chartrand, H. Kronk, and C. Wall. The point-arboricity of a graph. Israel J. Math., 6:169-175, 1968. [11] G. S. Domke, R. Laskar, S.T. Hedetniemi, and K. Peters. The partite chromatic number of a graph. Congr. Numer., 53:235-246, 1986. [12] F. Harary. Conditional colorability in graphs. Appears in Graphs and Applications: Proceedings of the First Colorado Symposium on Graph Theory. John Wiley and Sons Inc., New York, 1985. [13] F. Harary. Graph Theory. Addison-Wesley, Massachusetts, 1969.

PAGE 36

[14] F. Harary and K. l