Citation |

- Permanent Link:
- http://digital.auraria.edu/AA00001727/00001
## Material Information- Title:
- The conditional chromatic number of a graph
- Creator:
- Casey, Karen Lee
- Publication Date:
- 1990
- Language:
- English
- Physical Description:
- v, 31 leaves : illustrations ; 29 cm
## Thesis/Dissertation Information- Degree:
- Master's ( Master of science)
- Degree Grantor:
- University of Colorado Denver
- Degree Divisions:
- Department of Mathematical and Statistical Sciences, CU Denver
- Degree Disciplines:
- Applied mathematics
## 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 )
## Auraria Membership |

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( 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) 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) 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,- 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 [ 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,~ 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 |