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)