Choice Numbers, Ohba Numbers and Hall Numbers of some complete k-partite graphs Except where reference is made to the work of others, the work described in this dissertation is my own or was done in collaboration with my advisory committee. This dissertation does not include proprietary or classified information. (Julian) Apelete D. Allagan Certificate of Approval: Chris Rodger Professor Mathematics and Statistics Peter D. Johnson Jr. Chair Professor Mathematics and Statistics Dean G. Hoffman Professor Mathematics and Statistics George T. Flowers Dean Graduate School Choice Numbers, Ohba Numbers and Hall Numbers of some complete k-partite graphs (Julian) Apelete D. Allagan A Dissertation Submitted to the Graduate Faculty of Auburn University in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy Auburn, Alabama August 10, 2009 Choice Numbers, Ohba Numbers and Hall Numbers of some complete k-partite graphs (Julian) Apelete D. Allagan Permission is granted to Auburn University to make copies of this dissertation at its discretion, upon the request of individuals or institutions and at their expense. The author reserves all publication rights. Signature of Author Date of Graduation iii Dissertation Abstract Choice Numbers, Ohba Numbers and Hall Numbers of some complete k-partite graphs (Julian) Apelete D. Allagan Doctor of Philosophy, August 10, 2009 (M.A., Auburn University?Auburn, 2007) (B.S., Troy University?Troy, 2004) 51 Typed Pages Directed by Peter Johnson Jr. The choice numbers of some complete k?partite graphs are found, after we resolved a dispute regarding the choice number of K(4,2,...,2) when k is odd. Estimates of the choice numbers and the Ohba numbers of K(m,n,1,...,1) and K(m,n,2,...,2) are also discussed for various values of 1 ? n ? m. Finally we close this research with the Hall numbers of K(m,2,...,2) when m = 2,4. iv Acknowledgments I want to express my profound gratitude to Professor Vitaly Voloshin, who had taught me my first course in graph theory, and later had encouraged me to attend Auburn Uni- versity. I will remain forever grateful for having met him. Many thanks to you, Professor C. Rodger, not only for allowing me to come to Auburn, but also for your many academic advises and support during my stay here. Many thanks to you Professor D. Hoffman, for giving me a greater insight in solving graph theory problems through your advanced graph theory course. I remain indebt to the most patient and understanding advisor I could ever dream of. Professor P. Johnson, receive my deepest gratitude for your unconditional mul- tilateral support during this research. Thank you, Bertin and Dovi, for making it possible for me to come into this world. My gratitude to St Paul AME church for providing me with the right spiritual environment and many other supports during my stay in Troy. Many thanks to Mr and Ms Thomas for caring for me as their son, while I have been away from my hometown, Lome. Finally, this work will not be made possible without the motivation and the inspiration of many friends both here at Auburn and in Troy, particularly Edem, Abel and Bob. My love goes to Jennifer and Sophie, my two beautiful daughters and to the love of my life, Gabriela. I love you! v Style manual or journal used Journal of Approximation Theory (together with the style known as ?aums?). Bibliograpy follows van Leunen?s A Handbook for Scholars. Computer software used The document preparation package TEX (specifically LATEX) together with the departmental style-file aums.sty. vi Table of Contents List of Figures viii 1 Introduction 1 1.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Choice numbers 5 2.1 Choice number ? A dispute resolved . . . . . . . . . . . . . . . . . . . . . . 6 2.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.3 The dispute resolution . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Choice numbers and Ohba numbers . . . . . . . . . . . . . . . . . . . . . . 21 2.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.2 Choice numbers and Ohba numbers of K(m, n, 1,..., 1) . . . . . . . 22 2.3 An estimate of ch(K(m,2,...,2)) . . . . . . . . . . . . . . . . . . . . . . . . 28 2.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3 Hall numbers 31 3.1 Some necessary conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2 Hall numbers of some complete multipartite graphs . . . . . . . . . . . . . . 33 3.2.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.2.2 Some Hall numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Bibliography 42 vii List of Figures 1.1 K(3,3) minus two independent edges with a list assignment L. . . . . . . . . 2 2.1 A spanning subgraph of K(2,2,2). . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 An induced subgraph of the line graph of K(2,2,2). . . . . . . . . . . . . . . 7 3.1 A list assignment to K(2,2). . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 viii Chapter 1 Introduction Throughout this dissertation, the graph G = (V,E) will be a finite simple graph with vertex set V = V(G) and edge set E = E(G). 1.1 Basic definitions A complete k?partite graph G is a graph with k disjoint parts in which there is an edge between each pair of vertices of different parts and no other edges. When each part ofGhas size exactly one, G is said to be a complete graph. We use the notation K(m1,m2,...,mkbracehtipupleft bracehtipdownrightbracehtipdownleft bracehtipupright k ) to denote a complete k?partite graph (k ? 2) in which the parts have sizes m1,m2,...,mk. The complete graph on n vertices can be denoted by K(1,...,1), but is usually denoted by Kn. A collection of pairwise adjacent vertices forms a clique. An independent set (also known as a stable set) of a graph G is a set of vertices of G that are pairwise nonadjacent. The maximum size of such a set, denoted by ?(G), is called the independence number of G. A subgraph of the graph G is a graph H with V(H) ? V(G) and E(H) ? E(G). An induced subgraph H of G is the maximal subgraph of G with vertex set V(H). When we remove a vertex set, say V1 ?V(G), we write G?V1. For a single vertex, we write G?v. The line graph H of a graph G is the graph, often denoted by L(G), whose vertex set is the edge set of G; and two vertices are adjacent in H if and only if their corresponding edges share an endpoint in G. Let G1 and G2 be two graphs. The join of G1 and G2, denoted by G1 ?G2, is the graph H whose vertex set is V(H) = V(G1)?V(G2), a disjoint union, and whose edge set is E(G) = E(G1)?E(G2)?{v1v2 | v1 ?V(G1), v2 ?V(G2). 1 A list assignment to the graph G is a function L which assigns a finite set (list) L(v) to each vertex v ? V(G). A proper L?coloring of G is a function ? : V(G) ? uniondisplay v?V (G) L(v) satisfying, for every u, v ?V(G), (i) ?(v) ?L(v), (ii) uv ?E(G) ??(v) negationslash= ?(u). The choice number or list?chromatic number of G, denoted by ch(G), is the smallest integer k such that there is always a proper L?coloring of G if L satisfies |L(v)| ? k for every v ?V(G). We define G to be k?choosable if it admits a proper L?coloring whenever |L(v)| ?k for allv ?V(G); thench(G) is the smallest integerk such thatGisk?choosable. Since the chromatic number ?(G) is similarly defined with the restriction that the list assignment is to be constant, it is clear that for all G, ?(G) ? ch(G). There are many graphs whose choice number exceeds (sometimes greatly) their chromatic number. Figure 1.1 depicts the smallest graph G whose choice number exceeds its chromatic number. a115 a115 a115 a115 a115 a115u1 v2 u3 v1 u2 v3 {a,c} {a,b} {b,c} {b,c} {a,b} {a,c} Figure 1.1: K(3,3) minus two independent edges with a list assignment L. Notice that if we denote the parts of the bipartite graph K(3,3) by U = {u1,u2,u3} and V = {v1,v2,v3} for i = 1,2,3, then G?= K(3,3)?({u1v3}?{v1u3}). To see that G is not properly L?colorable, suppose that ? is a proper L?coloring of G. Now, if ?(u2) = b then ?(v2) = a and ?(v3) = c. Hence, we cannot properly color u1. On the other hand, if ?(u2) = a then ?(v2) = b and ?(v3) = c, and we cannot properly color u3. Hence, the graph G has no proper L?coloring and |L(v)| ? 2 for all v ? V(G). 2 Therefore, G is not 2?choosable, meaning ch(G) > 2. Further, since G is connected, and neither a complete graph nor an odd cycle, by Brooks? theorem for the choice number [3], ch(G) ? ?(G) = 3. Thus, ch(G) = 3. Any graph G for which the extremal case ?(G) = ch(G) holds is said to be chromatic? choosable. It is not hard to see that cycles, cliques and trees are all chromatic?choosable. (Well, the case of even cycles requires a little work. See [3].) 1.2 History In graph theory, a vertex coloring problem is the coloring of the vertices of a graph under various constraints, with the aim of optimizing something, so that adjacent vertices receive different colors. The classical constraint is that colors are chosen from a fixed palette, and the aim is to minimize the number of colors available. List colorings, as generalizations of the usual vertex coloring, were first introduced in the late 1970?s by Vizing [13], and then independently by Erd?os et al. [3] Erd?os et al were inspired by Jeffrey Dinitz? problem: if the cells of an n?n array are assigned sets of size n, can representatives of these sets necessarily be found for the cells so that no representative occurs more than once in any row or column of the array? Dinitz? problem turned out to be a very important list coloring problem which can be restated as follows: Is the line graph of the complete bipartite graph K(n,n) chromatic?choosable? The problem remained unsolved until 1995 when Frederick Galvin [4] proved that the line graph of any bipartite multigraph is chromatic?choosable. It is clear that Galvin?s result is much stronger than the original Dinitz? problem. However, there remains one fundamental unanswered ques- tion about the original list coloring problem of Vizing (in Russian): Is the line graph of any graph chromatic?choosable? The affirmative answer to that open question is famously known as the (edge) list coloring conjecture. Because it is very difficult to find the choice number of any graph, some mathematicians have begun to doubt the validity of the conjec- ture. Nevertheless, in 1995, Gravier and Maffray [5], after proving that every 3?chromatic claw?free perfect graph is chromatic?choosable, conjectured rashly that every claw?free 3 graph is chromatic?choosable; a much stronger conjecture than the list coloring conjecture since every line graph is claw?free. Their statement brings us back into considering the list coloring conjecture once again. Surveys of choice numbers of graphs can be found in [14] and [15]. In 2002, Ohba conjectured [11] that every graph G with 2?(G) + 1 or fewer vertices is chromatic?choosable. It is important to point out here that because every k?chromatic graph is a spanning subgraph of a complete k?partite graph, Ohba?s conjecture is true if and only if it?s true for every complete k?partite graph. Since then, several papers (see [8]) have been written specifically in attempts to find the choice numbers of some complete k?partite graphs which satisfy the hypothesis of Ohba?s conjecture. Meanwhile, in 2005, Reed and Sudakov [12] proved that G is chromatic?choosable when |V(G)| ? 53?(G)? 45, a much stronger hypothesis than Ohba?s. 1.3 Overview We began this research with the list coloring conjecture in mind. We hoped to at least verify the conjecture for the line graph of K(2,2,2). We were soon confronted by the grim difficulty of finding the choice number of any simple graph. But thanks to my advisor?s flexibility, we simply decided to try to learn from what others have done. Soon we came across the papers written by Enomoto et al [2] and Xu, Yang[16]. There seems to be a contradiction between the results of Enomoto et al and Xu, Yang. In section 2.1, we resolve some of the issues related to both authors? results. Later, one of the authors? remarks in [2] lead us to investigate the choice numbers of some particular multipartite graphs. Our findings are presented in section 2.2. We close the chapter with some estimates of the choice numbers that we could not determine exactly. In the final chapter, we present some results on another list coloring graph parameter, the Hall number, closely related to the choice number. 4 Chapter 2 Choice numbers In the first section of this chapter, we resolve a dispute over the choice number of the complete k?partite graph K(4,2,...,2) when k is odd. Further, in the same section, we revise the proof in [2] about the choice number of K(4,2,...,2) when k is odd. In the next section, estimates, and in some cases exact values, are obtained of the choice numbers of some complete multipartite graphs in which all parts except one are of sizes 1, 2 or 3. These results also estimate, and sometimes determine, the Ohba number of these graphs. The Ohba number of a (finite simple) graph is the smallest order of a clique such that the choice number and the chromatic number of the join of the graph with a clique of that order are equal. Here is some background on the choice numbers of some complete multipartite graphs. Theorem A.(Erd?os, Rubin and Taylor [3]) The completek?partite graphK(2,2,...,2) is chromatic?choosable. Notice that this result establishes that every simple graph with independence number 2 is k?choosable. This is due to the fact that every k?chromatic graph is a spanning subgraph of some complete k?partite graph, in which the parts are the color classes from some proper k?coloring of the original graph. Theorem B. (Gravier and Maffray [5]) If k > 2, then the complete k?partite graph K(3,3,2,...,2) is chromatic?choosable. This result does not hold for k = 2 since K(3,3) contains the subgraph in Figure 1.1, whose choice number is bigger than 2. 5 Corollary B. The complete k?partite graph K(3,2...,2) is chromatic?choosable. Since K(3,2...,2) is a complete k?partite graph, k = ?(K(3,2...,2)) ? ch(K(3,2...,2)). Further, K(3,2...,2) is a subgraph of the complete k?partite graph K(3,3,2,...,2). Therefore ch(K(3,2...,2)) ? k if k > 2. Thus, ch(K(3,2...,2)) = k if k > 2. When k = 2, we have K(3,2), of which it is well known that the choice number is 2. See [9], for instance. Theorem C.(Kierstead [10]) LetGdenote the completek?partite graphK(3,3,3,...,3). Then ch(G) = ceilingleft(4k?1)3 ceilingright. Observe that this result implies that ch(G) = k+ 1 when 2 ?k ? 4 and k+ 1 1,k ?ch(K(4,2,...,2)) ?k+1. (?) 11 Proof that ch(Gk) = k+ 1 if k is even. From the remark (?), when k is even it suffices to prove that ch(K(4,2,...,2)) >k. When k is even, Enomoto et al. give a list assignment to K(4,2,...,2) with all lists of length (cardinality) k from which no proper coloring is possible. Actually when k ? 2 and k is even, they give floorleftk4floorright+ 1 essentially different such list assignments, of the form of L0 in (??). We will go through the proof that when k is even, this list assignment to K(4,2,...,2) does not permit a proper coloring in order to contrast the situation with a challenge to the claim of Theorem 2.1 when k is odd; See claim A, below. Clearly|L0(v)| = kfor allv ?V(Gk). Any attempt to color the vertices ofK(4,2,...,2) from the list assignmentL0 will requirek?1 colors fromAfor theui andk?1 colors fromB for the vi, i = 2,...,k. Hence for the vertices in V1 there remains only one color a?A, and one color b?B. Let?s assume that a?A1 and b?B1; then x4 cannot be colored. Similarly if a ? A1 and b ? B2, we cannot color x3; and, similarly, for each of the remaining 6 cases a ? Ai, b ? Bj, some xt ? V1 cannot be colored. Thus, there is no proper L0?coloring of Gk and all lists are of length k. So, ch(Gk) = k+ 1 if k is even by the remark (?). Digression. Claim A( Xu, Yang [16](2007)) ch(K(4,2,...,2)) = k+ 1 for all k> 1. This claim contradicts the assertion of Theorem 2.1 when k is odd. In an attempt, albeit unsuccessful, to prove this claim when k is odd, Xu, Yang defined the following: LetAandB be disjoint sets of colors with |A| = k+1 and |B| = k?1. LetA1,A2,A3,A4 be disjoint sets of colors partitioning A such that |A1| = |A2| and |A3| = |A4|. Let B1, B2 be (k ? 1)/2 sets partitioning B and let 0 be a color in A. It is claimed that Gk has no proper Lprime?coloring where Lprime is a list assignment to Gk defined as follows: 12 1. Lprime(ui) = A?{0} and Lprime(vi) = B?{0}, for every 2 ?i?k and 2. Lprime(x1) = A1 ?A3 ?B1, Lprime(x2) = A1 ?A4 ?B2, Lprime(x3) = A2 ?A4 ?B1 and Lprime(x4) = A2 ?A3 ?B2. It is clear that|Lprime(ui)| = |Lprime(vi)| = kfor every 2 ?i?kand|Lprime(xi)| = (k+1)2 +(k?1)2 = k for all 1 ?i? 4. Without loss of generality we can assume that 0 ?A1. We show that Gk has a proper Lprime?coloring ?, given any such list assignment Lprime. Any proper coloring of the subgraph K(2,...,2) of Gk from the list assignment Lprime will require k?1 colors from A?{0} for the ui and k?1 colors from B?{0} for the vi, i = 2,...,k. Color the uiprimes with a k?1 subset of the k?color set A?{0} and color the viprimes with the k?1 colors of the set B. There remain unused exactly one color of A?{0}, say c, and 0 (since 0 did not appear as a color on any of the ui and vi, i = 2,...,k) to color the vertices of V1. By letting c ? A2, we can have ?(x3) = c = ?(x4) and ?(x1) = 0 = ?(x2) (since 0 ?A1), giving a proper coloring of Gk. Thus, the assertion of Xu, Yang about ch(K(4,2,...,2)) , when k is odd, is not proven by their list assignment, and the temptation is to dismiss it. Theorem 3 of [2] reads: Suppose that L is a list assignment of G = K(4,2,...,2) such that |L(v)| ?k for each v ?V(G). If G is not L?colorable, then L is essentially equivalent to L0 (??), namely, there exists a bijection ? of colors and automorphism ? of G satisfying ? ?L?? = L0. The proof in [2] is by induction on k, using the full conclusion of the theorem as the induction hypothesis. To put it another way, the theorem and the induction hypothesis could be: If k ? 1 is odd, then Gk is k?choosable, and if k ? 2 is even then the only list assignments L to Gk such that |L(w)| ? k for all w ? V(Gk), and there is no proper L?coloring of Gk, are equivalent to L0 in (??). 13 Resumption of the proof of Theorem 2.1 We go by induction on k, assuming as an induction hypothesis that ch(Gk) = k when k is odd. The case when k = 1 is trivial. Assume k ? 2. Let L be a list assignment to Gk = K(4,2,...,2) such that |L(v)| ?k for eachv ?V(G). Suppose thatGk has no proper L?coloring. We proceed by induction on k, but our only induction hypothesis is that for k odd, ch(Gk) = k. We will prove this and that when k is even, L(u1) = ... = L(uk) = A, L(v1) = ... = L(vk) = B (after renaming within each part, possibly), where A and B are disjoint k?sets. Then the conclusion for even k follows from Lemma 2.2 . Claim 2.1.1. intersectiondisplay x?V1 L(x) = ? Suppose that c ? intersectiondisplay x?V1 L(x). Let Lprime = L ? {c}. Color the vertices in V1 with c. Then, Gk ?V1 ?= K(2,2,...,2) has a proper Lprime?coloring since |Lprime(v)| ? k ? 1 for every v ?V(Gk ?V1). Thus, Gk has a proper L?coloring, a contradiction. We note here that the proof of Claim 2 in [2] (p.58) assumes as part of the induction hypothesis that when k is even, only for L of form L0 is Gk not properly L?colorable. Our aim here is to give the proof without this as part of the induction hypothesis. Our proof will be longer, but more credible. What follows is Claim 2 in [2], with a different proof. Claim 2.1.2. L(ui)?L(vi) = ? for each i? 2. When k = 2 this follows easily from the non L?colorability of Gk. So, we assume k ? 3. Suppose there is a color c ? L(uk) ?L(vk) . Color both uk and vk with c. Let Gk?1 = Gk ?Vk and Lprime = L? {c}. Then the list assignment Lprime satisfies the following assertions: (a) |Lprime(v)| ?k?1 since |L(v)| ?k for each v ?V(G). (b) Gk?1 has no proper Lprime?coloring since Gk has no proper L?coloring. (c) Lprime(ui)?Lprime(vi) = ? for each 2 ? i ? k?1: If k?1 were odd, then, by (a) and the induction hypothesis, Gk?1 would be properly Lprime?colorable, contradicting (b). Therefore, 14 k?1 is even. If, say, cprime ? Lprime(uk?1)?Lprime(vk?1), color uk?1, vk?1 with cprime, set Lprimeprime = Lprime ?{cprime} on Gk?2 = Gk?1 ?Vk?1; but then |Lprimeprime(v)| ?k?2 for each v ?V(Gk?2), and k?2 is odd, so Gk?2 is properly Lprimeprime?colorable by the inductive hypothesis. So (b) is contradicted again. (d) |Lprime(xj)| ?k for some 1 ?j ? 4 since c cannot appear on all lists in V1 by Claim 2.1.1. (e) The intersection of any three lists on V1 is empty. Suppose ?c?Lprime(x1)?Lprime(x2)?Lprime(x3). Then, we color x1,x2,x3 with ?c and the subgraph Gk?1 ?{x1,x2,x3} with the list assignment Lprime?{?c} satisfies the hypothesis of Lemma 2.1, by assertion (c) and Claim 2.1.1. Therefore Gk?1 is Lprime?colorable, a contradiction. (f)Lprime(xi)?Lprime(xj) negationslash= ?for someinegationslash= j; OtherwiseLprime(xi)?Lprime(xj) = ?for eachinegationslash= j. Then Gk?1 with Lprime satisfies the hypothesis of Lemma 2.1, and so Gk is properly Lprime?colorable, a contradiction. (g) If a?Lprime(x1)?Lprime(x2) then there exists b?Lprime(x3)?Lprime(x4). Suppose Lprime(x3)?Lprime(x4) = ?. Let Lprimeprime = Lprime ?a on V2 ?...?Vk?1 and Lprimeprime(xi) = Lprime(xi), i = 3,4. Then, the subgraph Gk?1 ? {x1,x2} satisfies the hypothesis of Lemma 2.1 and so Gk?1 ? {x1,x2} is properly Lprimeprime?colorable, and thus Gk?1 is properly Lprime?colorable, a contradiction. (h) Lprime(V1) ? Lprime(V2 ?...?Vk?1). Suppose there is a color c ? Lprime(xi) for some i and c /?Lprime(V2?...?Vk?1). Colorxi withc. Then|Lprime(xj)| ?k?1 for eachj negationslash= iand|Lprime(v)| ?k?1 for each v ? V2 ?...?Vk?1. By Corollary B, the subgraph G?xi ?= K(3,2...,2) has a proper Lprime?coloring, and therefore Gk?1 does also, a contradiction. We use the previous assertions to prove the following subclaims. Subclaim 1: If ? ?Lprime(x1)?Lprime(x2) and ? ?Lprime(x3)?Lprime(x4) then {?,?} ?Bprime for some (k?1)?set of colors Bprime, which is one of the lists on Vi for each i = 2,...,k?1. Proof. Note that ? negationslash= ?, by Claim 2.1.1. Color x1,x2 with ? and x3,x4 with ?. Let Lprimeprime = Lprime?{?,?} and H = Gk?1 ?V1. Then |Lprimeprime(v)| ? k? 3 for each v ? V(H). Because Lprime(vi) ?Lprime(ui) = ?, i = 2,...,k? 1, for each 15 i ? {2,...,k? 1}, either |Lprimeprime(ui)|, |Lprimeprime(vi)| ? k? 2, or one of |Lprimeprime(ui)|, |Lprimeprime(vi)| is equal to k? 3 and the other is greater than or equal to k? 1. If, say, |Lprimeprime(u2)|, |Lprimeprime(v2)| ? k? 2, then we can apply Lemma 2.1 to the complete (k ? 2)?partite graph H ?= K(2,...,2), with V2 playing the role of the first part, to conclude that H is properly Lprimeprime?colorable, a contradiction. Therefore, in each of V2,...,Vk?1, the Lprime list on one of the vertices , say Lprime(vj), contains ? and ?, and we have |Lprimeprime(vi)| ?k?3, |Lprimeprime(ui)| ?k?1. Since H has no proper Lprimeprime?coloring, there exists a nonempty set S ?V(H) such that |Lprimeprime(S)| ? |S|? 1. (This is by Hall?s theorem; see section 3.1.) Suppose Vj ? S for some j ? 2. Then k?1+k?3 = 2(k?2) ? |Lprimeprime(uj)|+|Lprimeprime(vj)| ? |Lprimeprime(S)| ? |S|?1 ? 2(k?2)?1, a contradiction. So, S contains at most one vertex of Vj for each j ? 2. Thus, |S| ?k?2. Further, since |Lprimeprime(v)| ? k?3 for each v ? V(H), |S| = k?2 and |Lprimeprime(S)| = k?3. Thus, S = {v2,...,vk?1} and Lprimeprime(v2) = ... = Lprimeprime(vk?1). Further, since Lprimeprime = Lprime ?{?,?}, we can conclude that Lprime(v2) = ... = Lprime(vk?1) = Bprime where Bprime is a (k? 1)?set of colors. As noted previously, ?, ? ?Bprime. Corollary: By the assertions (f), (g), and (e), and Subclaim 1, there is such a set Bprime. Subclaim 2: Lprime(u2) = ... = Lprime(uk?1) = Aprime, for some (k?1)?set of colors Aprime. Proof. Let ? ? Lprime(x1) ?Lprime(x2) and Bprime = Lprime(vi), i = 2,...,k ? 1 be as in Subclaim 1 and its corollary, so ? ? Bprime and |Bprime| = k ? 1. Then, Lprime(x3) \ Bprime negationslash= ? and Lprime(x4) \ Bprime negationslash= ? since ? /?Lprime(x3)?Lprime(x4) by the assertion (e). Hence there exist colors ?,? /?Bprime such that ? ? Lprime(x3) and ? ? Lprime(x4). Consider x1 and x2 to be colored with ?, x3 with ?, and x4 with ?. Define Gprime = Gk?1?V1 and Lprimeprime = Lprime?{?,?,?}. Since Gprime is not Lprimeprime?colorable, there exists a nonempty set S ?V(Gprime) such that |Lprimeprime(S)| ? |S|?1. Suppose Vj ?S for some j ? 2. Then (k? 1) ? 2 + (k? 1) ? 1 = 2k? 5 ? |Lprimeprime(uj)| + |Lprimeprime(vj)| ? |Lprimeprime(S)| ? |S|? 1 ? 2(k ? 2) ? 1. This implies that |S| = 2(k ? 2) and |Lprimeprime(S)| = 2k ? 5. It follows that 16 |Lprimeprime{u2,...,uk?1}| = k ? 3 and thus that Lprime(u2) = ... = Lprime(uk?1) = Lprimeprime(ui) ? {?,?}. From there and the fact that |Lprime(ui)| ? k ? 1, i = 2,...,k ? 1, it follows that Lprime(ui) = Lprimeprime(ui)?{?,?} = Aprime, i = 2,...,k?1, a (k?1)?set. On the other hand, ifS cannot contain bothuj andvj for for anyj ? 2, then (k?1)?2 ? |Lprimeprime(S)| ? |S|?1 ? (k?2)?1. This implies that |S| = (k?2) and |Lprimeprime(S)| = (k?1)?2 = |Lprimeprime(uj)| for every j ? 2. We can once again conclude that Lprime(u2) = ... = Lprime(uk?1) = Aprime, for some (k?1)?set of colors Aprime. Because |Lprime(xi)| = k for some i ? {1,2,3,4}, it now follows from Lemma 2.2, with k there replaced by k?1, that Gk?1 is properly Lprime?colorable after all, a contradiction. This establishes Claim 2.1.3, meaning L(ui)?L(vi) = ? for each i = 2,...,k. We proceed to prove the following sequences of claims which are very similar to the ones in [2]. They can also be easily derived as were the assertions (e), (f), (g), (h) in Claim 2.1.1 and the Subclaims 1 and 2 by lettingLandk play the roles ofLprime andk?1 respectively, and letting Claim 2.1.2 play the role played by (c) in the proof of Claim 2.1.2. Claim 2.1.3. The intersection of any three lists in V1 is empty. Suppose c?L(x1)?L(x2)?L(x3). Then, we color x1,x2,x3 with c and the subgraph Gk ?{x1,x2,x3} with Lprime = L?{c} satisfies the hypothesis of Lemma 2.1, by Claim 2.1.2; therefore Gk is properly L?colorable, a contradiction. Claim 2.1.4. L(xi)?L(xj) negationslash= ? for some inegationslash= j. Otherwise L(xi)?L(xj) = ? for each i negationslash= j. Thus, Gk with L satisfies the hypothesis of Lemma 2.1, and so Gk is properly L?colorable, a contradiction. Claim 2.1.5. If a?L(x1)?L(x2) then there exists b?L(x3)?L(x4). Suppose L(x3) ? L(x4) = ?. Let Lprime = L ? a on V2 ? ... ? Vk and Lprime(xi) = L(xi), i = 3,4 with Lprime. Then, the subgraph Gk ?{x1,x2} satisfies the hypothesis of Lemma 2.1 and so Gk ? {x1,x2} is properly Lprime?colorable, and thus Gk is properly L?colorable, a contradiction. 17 Claim 2.1.6. L(V1) ?L(V2 ?...?Vk). Suppose there is a color c?L(xi) for some i and c /?L(V2 ?...?Vk). Color xi with c. Then |L(xj)| ? k for each j negationslash= i and |L(v)| ? k for each v ? V2 ?...?Vk. By corollary B, the subgraph G?xi ?= K(3,2...,2) has a proper L?coloring, a contradiction. Subclaim 3: If ? ? L(x1) ?L(x2) and ? ? L(x3) ?L(x4) then {?,?} ? B for some k?set of colors B, which is one of the lists on Vi for each i = 2,...,k. Proof. Suppose ? ? L(x1) ? L(x2) and ? ? L(x3) ? L(x4). Then color x1,x2 with ? and x3,x4 with ?. Let Lprime = L ? {?,?} and H = Gk ? V1. Then |Lprime(v)| ? k ? 2 for each v ? V(H). Because L(vi) ?L(ui) = ?, i = 2,...,k, for each i ? {2,...,k}, either |Lprime(ui)|, |Lprime(vi)| ? k ? 1, or one of |Lprime(ui)|, |Lprime(vi)| is equal to k ? 2 and the other is greater or equal to k. If, say, |Lprime(u2)|, |Lprime(v2)| ?k?1, then we can apply Lemma 2.1 to the complete (k?1)?partite graphH ?= K(2,...,2), withV2 playing the role of the first part, to conclude that H is properly Lprime?colorable, a contradiction. Therefore, in each of V2,...,Vk, the L list on one of the vertices , say L(vj), contains ? and ?, and we have |Lprime(vi)| ? k ? 2, |Lprime(ui)| ?k, i = 2,...,k. Since H has no proper Lprime?coloring, there exists a nonempty set S ? V(H) such that |Lprime(S)| ? |S|?1. Suppose Vj ?S for some j ? 2. Then k +k? 2 = 2(k? 1) ? |Lprime(uj)| + |Lprime(vj)| ? |Lprime(S)| ? |S|? 1 ? 2(k? 1) ? 1, a contradiction. So, S contains at most one vertex of Vj for each j ? 2. Thus, |S| ? k? 1. Further, since |Lprime(v)| ? k? 2 for each v ? V(H), |S| = k? 1 and |Lprime(S)| = k? 2. Thus, S = {v2,...,vk} and Lprime(v2) = ... = Lprime(vk). Further, since Lprime = L?{?,?}, we can conclude that L(v2) = ... = L(vk) = B where B is a k?set of colors. As noted previously, ?, ? ?B. Corollary: By Claims 2.1.2 , 2.1.4, 2.1.5, and Subclaim 3, there is such a set B. Subclaim 4: L(u2) = ... = L(uk) = A, for some k?set of colors A. Proof. 18 Let ? ?L(x1)?L(x2) and B = L(vi), i = 2,...,k be as in Subclaim 3 and its corollary, so ? ? B and |B| = k. Then, L(x3) \B negationslash= ? and L(x4) \B negationslash= ? since ? /? L(x3) ?L(x4) by Claim 2.1.3 . Hence there colors ?,? /? B such that ? ? L(x3) and ? ? L(x4). Color x1 and x2 with ?, x3 with ?, and x4 with ?. Define Gprime = Gk ?V1 and Lprime = L?{?,?,?} as we color the vertices in V1. Since Gprime is not Lprime?colorable, there exists a nonempty set S ?V(Gprime) such that |Lprime(S)| ? |S|?1. Suppose Vj ?S for some j ? 2. Then k?2+k?1 = 2k?3 ? |Lprime(uj)|+|Lprime(vj)| ? |Lprime(S)| ? |S|?1 ? 2(k?1)?1. This implies that|S| = 2(k?1) and|Lprime(S)| = 2k?3. It follows that|Lprime{u2,...,uk}| = k?2. From there and the fact that |L(ui)| ?k, i = 2,...,k, it follows that L(ui) = Lprime(ui)?{?,?} = A, i = 2,...,k, a k?set. On the other hand, if S cannot contain both uj and vj for for any j ? 2, then (k)?2 ? |Lprime(S)| ? |S|?1 ? (k?1)?1. This implies that |S| = (k?1) and |Lprime(S)| = k?2 = |Lprime(uj)| for every j ? 2. We can once again conclude that L(u2) = ... = L(uk) = A, for some k?set of colors A. Thus, we have shown that L(ui) = A, L(vi) = B for each 2 ? i ? k, and by Claim 2.1.2, A?B = ?. Thus, we established the hypothesis of Lemma 2.2 with the list assignment L to Gk satisfying that |L(v)| ? k for each v ? V(Gk) and there is no proper L?coloring. By the conclusion of Lemma 2.2, k must be even and L must be equivalent to L0 in (??). This concludes the proof of Theorem 2.1. Corollary 2.1.1. ( Enomoto et al. [2](2002)) Let G denote the complete k?partite graph K(4,2,...,2,1). Then ch(G) = k. Proof. Whenkis odd, it is clear by Theorem 2.1 thatch(G) = ksincek = ?(K(4,2,...,2,1) ? ch(K(4,2,...,2,1)) ? ch(K(4,2,...,2,2)) = k. When k is even, the subgraph G?v is (k?1)?choosable, where v is the vertex of the part of size 1 . Hence k = ?(G) ?ch(G) ? k = k?1 + 1, again invoking Theorem 2.1. Therefore ch(G) = k for all k> 1. 19 Later in [16]( p. 61), Xu, Yang concluded thatch(K(4,3,2...,2)) = k+1 for allk> 1. This conclusion was based on their erroneous Claim A. There is no doubt that ch(K(4,3,2,...,2)) ? k+ 1 for all k > 1, since the k?partite graph K(4,3,2,...,2) is a subgraph of the complete (k+1)?partite graph K(4,2,...,2,1) the choice number of which is k+ 1 by corollary 2.1.1. Now, when k is even, k+ 1 = ch(K(4,2,...,2)) ?ch(K(4,3,2,...,2)) ?k+ 1. Thus, the assertion ch(K(4,3,2...,2)) = k+ 1 is true when k is even. However, when k is odd, it would have to be shown that ch(K(4,3,2...,2)) > k, something that Xu, Yang did not show, because their correction of Theorem 2.1 was invalid. We would have to provide a list assignment L with |L(v)| ? k, v ? V(K(4,3,2...,2)), for which there is no proper L?coloring of K(4,3,2...,2). (I personally do not think there is such list assignment.) Theorem 2.2. (Enomoto et al.[2]) LetGdenote the completek?partite graphK(5,2,...,2). Then ch(G) = k+ 1. Proof. G is a subgraph of the complete (k + 1)?partite graph K(3,2,2,...,2), the choice number of which is k+ 1 by corollary B. Hence ch(G) ?k+ 1. When k is even, k+1 = ch(K(4,2,...,2)) ?ch(K(5,2,...,2)). Hence ch(G) = k+1. When k is odd, Enomoto et al. gave the following list assignment: Let A and B be disjoint k? 1 sets of colors. Let A1, A2 and B1, B2 be disjoint k?12 sets of colors partitioning A and B respectively. Further, let C ? A?B with |C| = k and the color 0 /?A?B. Define an assignment L of G as follows: 1. L(ui) = A?{0} and L(vi) = B?{0}, for every 2 ?i?k and 2. L(x1) = A1 ?B1 ?{0}, L(x2) = A1 ?B2 ?{0}, L(x3) = A2 ?B1 ?{0}, L(x4) = A2 ?B2 ?{0} and L(x5) = C. It is not hard to see that there is no proper L?coloring of G. Thus, ch(G) >k. 20 Corollary 2.2.1. Let G denote the complete k?partite graph K(6,2,...,2). Then ch(G) = k+ 1. Proof. Since k + 1 = ch(K(5,2,...,2)) ? ch(K(6,2,...,2)), it is clear that ch(G) ? k + 1. Further, G is a subgraph of the complete (k+1)?partite graph K(3,3,2,...,2) which has choice number k+ 1 by Theorem B. Thus, ch(G) ?k+ 1. So, ch(G) = k+ 1. 2.2 Choice numbers and Ohba numbers 2.2.1 Introduction In 2002, Ohba [11] proved that for any given graph G, there exists an integer n0 such that for any n?n0, the join G?Kn satisfies ch(G?Kn) = ?(G?Kn). The Ohba number of G is the number ?(G) defined to be the smallest integer n for which ch(G?Kn) = ?(G?Kn). In particular when G is chromatic?choosable, ?(G) = 0. Observe that |V(G?Kn)| ? 2?(G?Kn)+1 if and only ifn? |V(G)|?2?(G)?1. Now, Ohba?s conjecture[11] states that if |V(G)| ? 2?(G) + 1, then G is chromatic?choosable. Thus, Ohba?s conjecture would imply that ?(G) ?max(0,|V(G)|?2?(G)?1) ?max(0,|V(G)|?5) for every graph G with an edge. Conversely, if ?(G) ? max(0,|V(G)|?2?(G)?1) for all G then Ohba?s conjecture is true. It is further clear that Ohba?s conjecture is true for every graph of order at most 5, since Figure 1.1 is known to be the smallest graph that is not chromatic?choosable, and it is of order 6. We present here findings of Ohba numbers of some complete k?partite graphs. Proposition 2.1. For any graph G, ?(G) ?ch(G)??(G). Proof. If G is chromatic?choosable, by the definition ?(G) = ch(G)??(G) = 0. 21 Suppose G is not chromatic?choosable. Then ch(G) > ?(G). Let s be the smallest positive integer such that ch(G?Ks) = ?(G?Ks). Since ?(G?Ks) = ?(G) + s, this implies that s = ch(G ? Ks) ? ?(G). Further, ch(G) ? ch(G ? Ks) for all s ? 1. So, s?ch(G)??(G). Thus, ?(G) ?ch(G)??(G). Proposition 2.2. Let G denote the complete k?partite graph K(4,2,2,...,2). Then ?(G) = ?? ? ?? 0 if k is odd 1 otherwise. Proof. From Theorem 2.1, when k is odd, ch(G) = k = ?(G). Thus, ?(G) = 0 by definition. When k is even, ch(G) > k. Further, ch(G ? K1) = ch(K(4,2,2,...,2,1)) = k + 1 = ?(G?K1) by corollary 2.1.1. Thus, ?(G) = 1 when k is even. 2.2.2 Choice numbers and Ohba numbers of K(m, n, 1,..., 1) We present the choice numbers of the complete k?partite graphs K(m,n,1,...,1) for various values of 1 ?n?mand their corresponding Ohba numbers. Pretty clearly, ifk?2 ? ?(K(m,n)) then ?(K(m,n,1,...,1)) = ?(K(m,n)) ? (k? 2). So, ?(K(m,n,1,...,1)) = max{0,?(K(m,n))?(k?2)}. Consequently, we just need ?(K(m,n)). Throughout this section, we denote the parts of the complete k? partite graph K(m,n,1,...,1) by V1,V2,...,Vs where V1 = {x1,...,xm}, V2 = {y1,y2,...,yn} and Vs = {vs} for s = 3,...,k. Theorem 2.3. Let G denote the complete k?partite graph K(m,n,1,...,1). Then ch(G) ?n+k?1 for all 1 ?n?m. Proof. 22 Whenk = 2, it is shown in [9] thatch(G) ?n+1 for allm?n. The proof for arbitrary k ? 2 will be similar. We denote Gprime = G?V1, where V1 is the part of G of size m, and let L be a list assignment to G with |L(v)| ? n+k ? 1 for each v ? V(G). Any proper L?coloring of Gprime uses at most n+k?2 distinct colors, say ?1,...,?n+k?2. Thus, for each v ?V1, |L(v)?{?1,...,?n+k?2}| ? 1, and so G is L?colorable. Hence ch(G) ?n+k?1. Corollary 2.3.1. Let G denote the complete k?partite graph K(m,1,1,...,1). Then ch(G) = k for all m? 1. Proof. From theorem 2.3 (when n = 1), ch(K(m,1,1,...,1) ? k + 1 ? 1 = k. Further, k = ?(K(m,1,...,1)) ? ch(K(m,1,1,...,1)), so we can conclude that ch(K(m,1,1,...,1)) = k. It is fair to point out that this result also follows from the fact that?(Km) = ch(Km) = 1. Lemma 2.3. Let H denote the complete (k ? 1)?partite graph K(2,1,...,1) with parts V1 = {y1,y2}, Vs = {vs}, for each s = 2,...,k ? 1. Let L be a list assignment to H satisfying that L(y1) = A and L(y2) = B for some disjoint k?sets of colors A and B, and |L(w)| ?k for each w ?V(H). Then the number of different color sets arising from proper L?colorings of H is at least k 2 + 3k 2 . Proof. Let Kk?2 ?= H?V1 and Ci,j = { color setsfromproper L?coloringsof Kk?2 withi element(s) from A, j element(s) from B }, with 0 ?i,j ?k?2 and i+j ?k?2. Claim 1. summationdisplay 0?i,j?k?2 i+j?k?2 ci,j ? parenleftbiggk 2 parenrightbigg where ci,j = |Ci,j|. The number of proper L?colorings of Kk?2 is at least k(k ? 1)...(k ? (k ? 3)) = k(k?1)...3 = k!2 . Further, since each color set appears at most (k?2)! times, the number of distinct color sets arising from the proper L?colorings is at least k!2(k?2)! , meaning summationdisplay 0?i,j?k?2 i+j?k?2 ci,j ? k!2(k?2)! = parenleftbiggk 2 parenrightbigg . 23 DefineDp,q = {colorsetsfromproperL?coloringsof Hwithpelement(s)fromA, q element(s) from B }, with 1 ? p,q ? k, p+q ? k and let dp,q = |Dp,q|. Then the total number of color sets from proper L?colorings of H is summationdisplay 1?p,q?k p+q?k dp,q. Since any coloring of H uses exactly one color from A on y1 and one color from B on y2, every color set in Dp,q is of the form D = C ?{a,b} for some a ? A\C and b ? B\C and C ? Cp?1,q?1. For each 1 ? p,q ? k, p+q ? k, consider the bipartite graph with bipartition Dp,q, Cp?1,q?1 with D ? Dp,q, C ? Cp?1,q?1 adjacent if and only if C ? D. Now each C ? Cp?1,q?1 has degree (k?(p?1))(k?(q?1)) and each D ? Dp,q has degree at most pq in this bipartite graph. Therefore pqdp,q ? summationdisplay D?Dp,q deg(D) = summationdisplay C?Cp?1,q?1 deg(C) = (k?p+ 1)(k?q+ 1)cp?1,q?1. Thus, the total number of proper L?coloring sets satisfies summationdisplay 1?p,q?k p+q?k dp,q ? summationdisplay 1?p,q?k p+q?k (k?p+ 1)(k?q+ 1) pq cp?1,q?1. (2.1) Claim 2. f(p,q) ? (k+ 2) 2 k2 where f(p,q) = (k?p+ 1)(k?q+ 1) pq , 1 ? p,q ? k and p+q ?k. Fix s? {2,...,k} and consider values of p and q such that p+q = s. Then p = s?q, and 1 ?q ?s?1. Now, f(p,q) = f(s?q,q) = g(q) = (k+ 1?s+q)(k+ 1?q)(s?q)q . Also, we note that g(1) = g(s?1) = k(k+ 2?s)(s?1) , and gprime(q) = h(q)[(s?q)q]2 where h(q) = ?(k+1)(k+1?s)[s? 2q]. Therefore, g achieves a minimum on [1,s?1] at q = s/2. We have for all q ? [1,s?1], f(s?q,q) ?g(s/2) = f(s/2,s/2) = (k+ 1?s/2) 2 s2/4 . Clearly this minimum decreases as s increases. Therefore, for all p,q ? {1,...,k?1}, p+q ?k, f(p,q) ?f(k/2,k/2) = (k/2 + 1) 2 k2/4 = (k+ 2)2 k2 . From Claim 2 and the inequality 2.1, 24 summationdisplay 1?p,q?k p+q?k dp,q ? (k+ 2) 2 k2 ? summationdisplay 0?i,j?k?2 i+j?k?2 ci,j ? (k+ 2) 2 k2 ? k! 2(k?2)! = k2 + 3k 2 ? 2 k. Hence for all k ? 3, the number of different color sets arising from proper L?colorings of H is at least k 2 + 3k 2 . Theorem 2.4. Let G denote the complete k?partite graph K(m,2,1,...,1), k ? 3. Then ch(G) = ?? ? ?? k if m< k 2 + 3k 2 k+ 1 if m?k2. Proof. Let L be a list assignment to G with |L(v)| = k for each v ?V(G). Suppose G has no proper L?coloring. Observe that L(y1) ?L(y2) = ?. Otherwise there is a color c ? L(y1) ?L(y2). Then we can color y1 and y2 with c and the remaining subgraph G?V2 = K(m,1,...,1) can be colored from L?{c} because ch(G?V2) = k?1. Let H = G?V1. Since L(y1)?L(y2) = ?, by Lemma 2.3, the number of distinct sets arising from the proper L?colorings of the subgraph H is at least k 2 + 3k 2 . Further, G is not L?colorable if and only if the set of colors, which will be of size k, of each of the proper colorings of H occurs as a list in V1. Therefore for m< k 2 + 3k 2 , G is L? colorable. Thus, if m< k 2 + 3k 2 , ch(G) ? k. Also k = ?(G) ? ch(G), so ch(G) = k if m< k 2 + 3k 2 . When m = k2, we provide the following list assignment Lprime to V(G) for which there is no proper Lprime?coloring. Let A and B be disjoint sets of colors of size k, say A = {?1,...,?k} and B = {?1,...,?k}. Let Lprime(y1) = Lprime(v3) = ... = Lprime(vk) = A, Lprime(y2) = B. 25 Any coloring of H = K(2,1,...,1) requires exactly k?1 colors from A and one color from B, and there are exactly k2 color sets from such colorings. Let m = k2 lists on V1 be the k2 different sets (A\{?i})?{?i}, 1 ?i,j ?k. Since each of the proper colorings of H occurs as a list in V1, ch(K(m,2,1,...,1)) >k for m = k2. Further, by theorem 2.3, ch(K(m,2,1,...,1)) ? k + 1 for all m. This concludes the proof. Corollary 2.4.1. Ohba?s conjecture holds for the completek?partite graphK(m,2,1,...,1) with m?k+ 1. Proof. We denote G = K(m,2,1,...,1). Observe that when m ? k+ 1, |V(G)| ? (k+ 1) + 2 + (k? 2) = 2k + 1 = 2?(G) + 1. Thus, G satisfies the hypothesis of Ohba?s conjecture. Further, it is clear that k + 1 ? k 2 + 3k 2 ? 1 for all k ? 2. Thus, by theorem 2.4, G is chromatic?choosable when m?k+ 1. Corollary 2.4.2. floorleft?mfloorright?1 ??(K(m,2)) ? ceilingleft?7+ ?8m+17 2 ceilingright for m? 5. Proof. If k ? floorleft?mfloorright, then k2 ? m, so by Theorem 2.4 k + 1 = ch(K(m,2,1...,1)) > ?(K(m,2,1...,1)) = k. Thus, ifk ? floorleft?mfloorright,?(K(m,2)) ? (k?2)+1 = k?1. Consequently, ?(K(m,2)) ? floorleft?mfloorright?1, for all m ? 1. Further, by Theorem 2.4, if m ? k 2 + 3k 2 ?1 and k ? 3, then ?(K(m,2)) ?k?2. The smallest positive value of k for which m? k 2 + 3k 2 ?1 is the positive solution of k2+3k?2(m+1) = 0, so the smallest integer value of k satisfying that inequality is k0 = ceilingleft?3+ ?8m+17 2 ceilingright; we have ?(K(m,2)) ? k0 ? 2 = ceilingleft ?7+?8m+17 2 ceilingright. The requirement m? 5 ensures that k0 ? 3. Remark: ?(K(m,2)) = 1 for 4 ? m ? 8, by Theorem 2.4 and the previously noted fact that ch(K(m,2)) = 3 for all m? 4. 26 Lemma 2.4. Let G denote the complete k?partite graph K(m,3,1,...,1), L a list assign- ment to G satisfying that L(yi) ?L(yj) negationslash= ? for some yi negationslash= yj ? V2 and |L(v)| ? k + 1 for each v ?V(G). Then G is L?colorable for all m? 1. Proof. Suppose c1 ? L(y1)?L(y2) and say c2 ? L(y3) with c1 negationslash= c2. We color the vertices in V2 with c1 and c2. Let Gprime = G?V2 and Lprime = L?{c1,c2}. Then |Lprime(v)| ?k+1?2 = k?1 for each v ? V(Gprime). By Corollary 2.3.1, Gprime has a proper Lprime?coloring for all m ? 1. Thus, G is properly L?colorable. In the case that intersectiondisplay y?V2 L(y) negationslash= ?, it is clear from the previous argument that G is L?colorable for all m? 1. Theorem 2.5. Let G denote the complete k?partite graph K(m,n,1,...,1), and 2 ?n?m. Then ch(G) = n+k?1 if m? parenleftbiggn+k?2 k?1 parenrightbigg (n+k?2)n?1. Proof. Let C1,C2,...,Cn be disjoint (n+k?2)?sets of colors. We provide the following list assignment L to G, with |L(v)| = n + k ? 2 for each v ?V(G) as follows: L(y1) = L(v3) = ... = L(vk) = C1 and L(yj) = Cj for each 2 ?j ?n. L on V1 will be described shortly. Any proper L?coloring of Gprime = G?V1 ?= K(n,1,...,1) requires exactly k? 1 colors from C1 and exactly one color from each Cj for 2 ?j ?n , givingparenleftbigg n+k?2 k?1 parenrightbigg (n+k?2)n?1 distinct sets of colors from proper L?colorings, each set of size k. Let parenleftbiggn+k?2 k?1 parenrightbigg (n+k? 2)n?1 lists on V1 be the parenleftbiggn+k?2 k?1 parenrightbigg (n+k? 2)n?1 different sets of colors from such proper L?colorings of Gprime, and if m> parenleftbiggn+k?2 k?1 parenrightbigg (n+k?2)n?1, let the remaining vertices in V1 be supplied with any lists whatever of size n + k ? 2. Since each of the parenleftbiggn+k?2 k?1 parenrightbigg (n + k ? 2)n?1 sets of proper colorings of Gprime occurs as a list in V1, G cannot be properly L?colored, so ch(K(m,n,1,...,1)) > n+k? 2 for m ? 27 parenleftbiggn+k?2 k?1 parenrightbigg (n+k?2)n?1. Further, from Theorem 2.3, ch(G) ? n+k?1 for all m ? 2. Thus, for m? parenleftbiggn+k?2 k?1 parenrightbigg (n+k?2)n?1, ch(G) = n+k?1. Corollary 2.5.1. With G, m, n and k as in the hypothesis of Theorem 2.5, if 2 ?r ?n?1 and m? parenleftbiggr+k?2 k?1 parenrightbigg (r+k?2)r?1, then ch(G) ?r+k?1. Proof. When m ? parenleftbiggr+k?2 k?1 parenrightbigg (r+k? 2)r?1, ch(K(m,r,1,...,1)) = r+k? 1 by Theorem 2.5. Further, with 2 ? r ? n ? 1 < m, K(m,r,1,...,1) is a subgraph of the graph G = K(m,n,1,...,1). Corollary 2.5.2. With G, m, n and k as in the hypothesis of Theorem 2.5, if 2 ? r ? n and m? parenleftbiggr+k?2 k?1 parenrightbigg (r+k?2)n?1, then ?(G) ?r?1. Proof. By Proposition 2.1, ?(G) ?ch(G)??(G). Therefore ?(G) ?r+k?1?(k) = r?1. 2.3 An estimate of ch(K(m,2,...,2)) 2.3.1 Introduction Throughout this section, [n] = {1,...,n} and parenleftbigg[n] t parenrightbigg = {t?subsets of [n]}. For n ? m ? t ? 0, the covering number C(n,m,t) is defined by C(n,m,t) = min{|F|; F ? parenleftbigg[n] m parenrightbigg and ? B ? parenleftbigg[n] t parenrightbigg ,? A? F such that B ?A}. Proposition 2.3. Let G denote the complete k?partite graph K(m,2,2,...,2). Then ch(G) ? 2k?1. Proof. Let L be a list assignment to G such that |L(v)| ? 2k?1 for each v ? V(G). Any proper L?coloring of G?V1 ?= K(2,...,2) uses at most 2(k? 1) distinct colors say 28 ?1,...,?2k?2. Thus, for eachv ?V1, |L(v)?{?1,...,?2k?2}| ? 1, and soGisL?colorable. Hence ch(G) ? 2k?1. Lemma 2.5. C(n,m,t) is also the smallest size of a collection Fprime of n?m subsets of [n] (or any other fixed n?set) such that for every (n?t)?set Bprime ? parenleftbigg [n] n?t parenrightbigg , some Aprime ? Fprime is contained in Bprime. Proof. Given F, as in the original definition of C(n,m,t), form Fprime = {[n] \ A | A ? F}, the collection of complements of sets in F. Similarly, given Fprime ? parenleftbigg [n] n?m parenrightbigg , form F = {[n]\Aprime | Aprime ? Fprime}, the collection of complements of sets in Fprime. Because |F| = |Fprime|, in each case, and because complementation reverses inclusion, verification of the lemma?s claim is straightforward. Theorem 2.6. Let G denote the complete k?partite graph K(m,2,...,2) and k ? r ? 2k?2. If m?C(r,ceilingleftr/2ceilingright,r?k+1).C(r,floorleftr/2floorright,r?k+1) then ch(K(m,2,...,2)) ?r+1. Proof. Let A, B be disjoint r?sets. Denote by V1,V2,...,Vk the parts of G, with V1 = {x1,...,xm}, Vi = {ui,vi}, i = 2,...,k. Start defining a list assignment to G by assigning A to each ui and B to each vi. By Lemma 2.4, we can find a family F1 of r ? floorleftr/2floorright = ceilingleftr/2ceilingright?subsets of A and a family F2 of r ? ceilingleftr/2ceilingright = floorleftr/2floorright?subsets of B such that every r?(r?k+1) = (k?1)?subset of A contains some set in F1, and every (k?1)?subset of B contains some set in F2, and |F1| = C(r,ceilingleftr/2ceilingright,r?k+ 1), |F2| = C(r,floorleftr/2floorright,r?k+ 1). Make |F1|.|F2| lists of length r by forming the unions F1 ? F2, F1 ? F1, F2 ? F2. If m ? |F1|.|F2| then we can endow V1 with these lists. Then for every proper coloring of G \ V1, some list on V1 is in the set of colors used. Hence ch(K(m,2,...,2)) > r for m?C(r,ceilingleftr/2ceilingright,r?k+ 1).C(r,floorleftr/2floorright,r?k+ 1). 29 Corollary 2.6.1. If m? parenleftbigg2k?2 k?1 parenrightbigg2 then ch(K(m,2,...,2)) = 2k?1. Proof. For r = 2(k ? 1), if m ? C(2k ? 2,k ? 1,k ? 1)2 = parenleftbigg2k?2 k?1 parenrightbigg2 then ch(K(m,2,...,2)) ? 2k ? 1 by Theorem 2.6. Further, using Proposition 2.3, we estab- lish that ch(K(m,2,...,2)) = 2k?1. 30 Chapter 3 Hall numbers 3.1 Some necessary conditions Theorem 3.1. (P.Hall [6]). Suppose A1,A2,...,An are (not necessarily distinct) finite sets. There exist distinct elements a1,a2,...,an such that ai ? Ai, i = 1,2,...,n if and only if for each J ? {1,2,...,n}, | uniondisplay j?J Aj| ? |J|. A proper L?coloring of a complete graph Kn is certainly a system of distinct repre- sentatives of the finite list L(v), and any list A1,A2,...,An of sets can be regarded as lists assigned to Kn. Therefore, as noted in [7], Hall?s theorem can be restated as: Theorem 3.2. (Hall?s theorem restated). Suppose that L is a list assignment to Kn. There is a proper L?coloring of Kn if and only if, for all U ?V(Kn), |L(U)| = | uniondisplay u?U L(u)| ? |U|. Let L be a list assignment to a simple graph G, H a subgraph of G and P = {1,2,...} a set of colors. If ? : V(G) ? P is a proper L?coloring of G, then for any subgraph H ?G, ? restricted to V(H) is a proper L?coloring of H. For any ? ? P, let H(?,L) = < {v ? V(H) | ? ? L(v)} > denote the subgraph of H induced by the support set {v ?V(H) | ? ?L(v)}. For convenience, we sometimes simply write H?. For each ? ? P, ??1(?) = {v ? V(H) | ?(v) = ?} ? V(G?) and ??1(?) is an independent set. Further, ??1(?)?H ?V(H?). So, |??1(?)?H| ??(H?) where ? is the vertex independence number. This implies that summationdisplay ??P ?(H?) ? summationdisplay ??P |??1(?)?H| = |V(H)| for all H ?G. 31 When G and L satisfy the inequality summationdisplay ??P ?(H?) ? |V(H)| (3.1) for each subgraph H of G, they are said to satisfy Hall?s Condition, a necessary condi- tion for a proper L?coloring of G. Because removing edges does not diminish the vertex independence number, for G and L to satisfy Hall?s Condition it suffices that (3.1) holds for all induced subgraphs H of G. Hall?s Condition is sufficient for a proper coloring when G = Kn, because if H is an induced subgraph of Kn then ?(H?) = ? ??? ??? 1 if ? ? uniondisplay v?V (H) L(v), for each ? ? P, 0, otherwise. So summationdisplay ??P ?(H?) = | uniondisplay v?V (H) L(v)|; therefore Hall?s Condition, that summationdisplay ??P ?(H?) ? |V(H)| for every such H, is just a restatement of the condition in Theorem 3.2. (It is necessary to point out here that if ? /? L(v) for some v ? V(H) then H? is the null graph, and ?(H?) = 0.) Consequently, Hall?s Theorem may be restated: For complete graphs, Hall?s Condition on the graph and a list assignment suffices for a proper coloring. The temptation to think that there are many graphs for which Hall?s Condition is sufficient can be easily dismissed. Figure 3.1 is the smallest graph with a list assignment L0 for which Hall?s Condition holds, and yet G has no proper L0?coloring. Remark. 32 It is clear that if H is an induced subgraph of G and H negationslash= G, then H ?G?v for some v ?V(G). So, if G?v has a proper L?coloring, then H ?G?v must satisfy (by necessity) (3.1). Thus, in practice, in order to show that G and L satisfy Hall?s Condition, it suffices to verify that G?v is properly L?colorable for each v ? V(G) and that G itself satisfies the inequality (3.1) . Denoted by h(G), the Hall number of a graph G is the smallest positive integer k such that there is a proper L?coloring of G, whenever G and L satisfy Hall?s Condition and |L(v)| ?k for each v ?V(G). In [7] the following facts are shown: 1. If |L(v)| ??(G) for every v ?V(G) then G and L satisfy Hall?s Condition. 2. h(G) ?ch(G) for every G. 3. If ch(G) >?(G) then h(G) = ch(G). 4. If h(G) ??(G) then ?(G) = ch(G). These facts underline our findings in the next section. 3.2 Hall numbers of some complete multipartite graphs Throughout this section, G is a simple graph and L is a list assignment to V(G) such that L(v) ? {1,2,...,} = P, an integer set of symbols. If ? /? L(v) for some v ? V(G), then G? is the null graph. Further, we denote by ?(v), any attempted proper coloring of some v ?V(G). 3.2.1 Example Consider the complete bipartite graph K(2,2) in Figure 3.1 with parts Vi = {ui,vi}, i = 1,2 and L0 the list assignment indicated. 33 a115 a115 a115 a115u1 v2 u2 v1 {a,b} {b,c} {a,c} {c} Figure 3.1: A list assignment to K(2,2). If v1 is colored c, as it must be, then u2 must be colored a and v2 must be colored b in a proper coloring, so u1 cannot be properly colored. However, we will show that G and L0 satisfy Hall?s Condition using the argument described in the previous remark. First, for each v ? V(G), it is easy to see that G?v is properly L0?colorable, meaning every proper induced subgraph H ? G satisfies the inequality (3.1) in Hall?s Condition. We now proceed to verify the inequality (3.1) for G itself. Now, ?(Gc) = 2 and ?(Gb) = ?(Ga) = 1. So, 4 = summationdisplay ??P ?(G?) ? |V(G)| = 4 where P = {a,b,c,...}. Thus, G and L0 satisfy Hall?s Condition and yet G has no proper L0?coloring. Thus, 1 , an induced subgraph ofH. Thenk?2 = |A| = | uniondisplay v?V (S) Lprime(v)|< |V(S)| = k?1. Since the subgraph S is a clique, we cannot properly color S from Lprime. Case 2: ?(u1) = a and ?(v1) = c. Similarly as described in case 1, by letting S =< {u2,...,uk} >, it?s clear that we cannot properly color S, from Lprime. Case 3: ?(u1) = ? or ?(v1) = ? for some color ? ?A. Similarly as in case 1, k ? 2 = | uniondisplay v?V (S) Lprime(v)| < |V(S)| = k ? 1. Hence we cannot properly color H from Lprime. Claim 3.3.2. summationdisplay ??P ?(G?) ? |V(G)|. Proof. It is clear that ?(Ga) = ?(Gc) = 1,?(Gb) = 2; further, ?(G?) = 2(k ? 2) for every ? ?A. Hence summationdisplay ??P ?(G?) = 2k = |V(G)|. 35 Claim 3.3.3. Every proper induced subgraph H of G is properly L?colorable. Proof. In the following cases we provide a (not necessarily unique) proper coloring for each induced subgraph H of G, of the form G?v, v ?V(G). Case 1: H = G?u1. Let ?(v1) = c and color the 2(k ? 2) vertices of the subgraph G ? (V1 ? V2) with the colors from A (by coloring vertices of the same part with the same color). Then let ?(u2) = a and ?(v2) = b. Case 2: H = G?v1. Let ?(u1) = a and color the 2(k?2) vertices of the subgraph G?(V1 ?Vk) with the colors from A with the same color appearing on ui and vi, i = 2,...,k ? 1. Then, let ?(uk) = c and ?(vk) = b. Case 3: H = G?ui, for some 2 ?i?k. Let ?(vi) = b and color the remaining 2(k?2) vertices of the subgraph G?(Vi ?V1) with the colors from A. Then, let ?(u1) = a and ?(v1) = c. Case 4: H = G?vi, for some 2 ?i?k?1. Let ?(ui) = a and color the remaining 2(k?2) vertices of the subgraph G?(Vi ?V1) with the colors from A. Then, let ?(u1) = ?(v1) = b. Case 5: H = G?vk. Let ?(uk) = c and color the 2(k?2) vertices of the subgraph G?(V1 ?Vk) with the colors from A. Finally, let ?(u1) = ?(v1) = b. From the previous claims, we can conclude that h(G) > k? 1. Thus, by Theorem A and Fact 2, h(G) = k. This concludes the proof. 36 Theorem 3.4. Let G denote the complete k?partite graph K(4,2,...,2) with k ? 2. Then h(G) = ? ?? ?? k if k is odd k+ 1 if k is even. Proof. When k is even, from Chapter 2 we have that k = ?(G)