SOME NECESSARY CONDITIONS FOR LIST COLORABILITY OF GRAPHS
AND A CONJECTURE ON COMPLETING PARTIAL LATIN SQUARES
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.
Benkam Benedict Bobga
Certificate of Approval:
Dean G. Hoffman,
Professor
Mathematics and Statistics
Peter D.Johnson Jr., Chair
Professor
Mathematics and Statistics
Overtoun M. Jenda,
Professor
Mathematics and Statistics
George T. Flowers,
Interim Dean
Graduate School
SOME NECESSARY CONDITIONS FOR LIST COLORABILITY OF GRAPHS
AND A CONJECTURE ON COMPLETING PARTIAL LATIN SQUARES
Benkam Benedict Bobga
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
December 19, 2008
SOME NECESSARY CONDITIONS FOR LIST COLORABILITY OF GRAPHS
AND A CONJECTURE ON COMPLETING PARTIAL LATIN SQUARES
Benkam Benedict Bobga
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
SOME NECESSARY CONDITIONS FOR LIST COLORABILITY OF GRAPHS
AND A CONJECTURE ON COMPLETING PARTIAL LATIN SQUARES
Benkam Benedict Bobga
Doctor of Philosophy, December 19, 2008
(M.S., East Tennessee State University,?U.S.A 2005)
(M.Sc.,Buea University?Cameroon, 1998)
(B.Sc (Honors)., Buea University?Cameroon, 1996)
87 Typed Pages
Directed by Peter D. Johnson Jr.
Let C be an infinite set of symbols, F the collection of finite subsets of C. A function
L is a list assignment to a graph G if L assigns to each vertex of G a finite subset of C.
A proper L-coloring occurs when adjacent vertices are colored with different colors from
their corresponding lists. Interpreted as a theorem about proper list colorings of complete
graphs, P. Hall?s theorem on systems of distinct representatives inspires a generalization, a
necessary condition for proper colorings, known as Hall?s Condition (HC). The problem of
completing an n?n partial latin square (PLS) is a list coloring problem in which G is the
cartesian product of two n-cliques and L is determined in an obvious way.
Cropper?s problem is the question: does a completion exist whenever the associated
list coloring problem satisfies Hall?s Condition? One will show that HC is sufficient for com-
pletion of a PLS in several circumstances addressed in well established theorems, including
Ryser?s theorem. Generalizations of Cropper?s problem and refinements of HC for colorings
recently developed by Hilton, Johnson, Lehel et al, completes this dissertation.
iv
Acknowledgments
My first appreciation go to all the members of the committee for their time and energy
reading through this work. The vital corrections from them are greatly appreciated. I
would also like to acknowledge the help of Professors A.J.W. Hilton, Chris Rodger and D.
Leonard for their separate contribution to this work. Their advice and critique on both the
work on latin squares and Hall?s condition are greatly appreciated
Needless to say the maximum input from Professor Johnson, my advisor and supervisor,
deserves very special appreciation. Professor Johnson was always there to point out the flaws
or missing pieces in my proofs. Most of the material used for this research was from his
personal collection of topics and problems.
Finally, I will like to thank my family both here and abroad (Cameroon) for their
special prayers and advice. I very much appreciate my family?s understanding during those
occasions that they had to make-do without a full time FATHER, HUSBAND or son that
I became due to this work. These 3 years in Auburn have been very challenging but my
family was always there either physically, by phone or by emails, to make me smile and to
know that all will be well.
This work is dedicated as a special birthday present to all my lovely children.
Thank you for every thing. Yours BOBGA, Benkam B.
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 AND BACKGROUND KNOWLEDGE 1
2 CROPPER?S PROBLEM AND RECASTED RESULTS 17
2.1 Introduction to Cropper?s Problem . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Cropper?s Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Recasted Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.1 Recasting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.2 Hoffman?s Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.3.3 Another look at Ryser?s Theorem . . . . . . . . . . . . . . . . . . . . 45
3 HALL+ AND HALL++ GRAPHS 47
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2 Inclusion Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.3 Forbidden Induced Subgraph Characterization . . . . . . . . . . . . . . . . 50
3.4 Closure Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4 HALL* AND HALL** GRAPHS 65
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.2 Closure Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Bibliography 77
vii
List of Figures
1.1 K4 - minus - an edge with assigned list . . . . . . . . . . . . . . . . . . . . . 3
1.2 K3,3minus two independent edges with a list assignment with lists of length
2 from which no proper coloring is possible. . . . . . . . . . . . . . . . . . . 4
1.3 Four Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1 An Incomplete PLS with some lists indicated . . . . . . . . . . . . . . . . . 19
2.2 7?7 partial latin square. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 A partial latin square with its accompanying list assignment. . . . . . . . . 22
2.4 Bad set indicated by the lists from figure (2.2). . . . . . . . . . . . . . . . . 23
2.5 Rectangular blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.6 Rectangular blocks with R and C filled-in . . . . . . . . . . . . . . . . . . . 31
2.7 Rectangular blocks with S and local diagonals filled-in . . . . . . . . . . . . 33
2.8 t?t square with block R and main diagonal D filled-in . . . . . . . . . . . 34
2.9 t?t square with indicated H(k) filled-in . . . . . . . . . . . . . . . . . . . . 37
2.10 n?n commutative square with block A and main diagonal filled-in . . . . . 40
2.11 Randomly filled-in 5 ? 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.12 Column latin 5 ? 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.13 Randomly filled-in 5 ? 6 Rectangle . . . . . . . . . . . . . . . . . . . . . . . 43
2.14 5 ? 6 Latin Rectangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.15 Rows ri and symbols sj in the array. . . . . . . . . . . . . . . . . . . . . . . 45
3.1 G = K2 V K10 with assigned list. . . . . . . . . . . . . . . . . . . . . . . 49
viii
3.2 Hall+ graph H, with an attached clique hatwideK . . . . . . . . . . . . . . . . . . . 55
3.3 Hall+ graph H ? hatwideH1 and clique hatwideK . . . . . . . . . . . . . . . . . . . . . . . 58
3.4 Cycle with n vertices, Cn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.5 K4 - minus - an edge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.6 Attached Hall+ graphs at vertex v that does not yield a Hall+ graph . . . 64
4.1 3? 2 Rectangle of cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2 3? 2 Rectangle of cells with no completion . . . . . . . . . . . . . . . . . . 67
4.3 Hall* graph H, with an attached clique hatwideK . . . . . . . . . . . . . . . . . . . 68
4.4 Hall* graph H ? Hprime ? Tprime, and clique hatwideK . . . . . . . . . . . . . . . . . . . . 69
ix
Chapter 1
INTRODUCTION AND BACKGROUND KNOWLEDGE
Graph List Coloring was introduced in the late 1970s independently by Vizing [20] with
the intention to study total colorings, and Erd?os, Rubin and Taylor [9] with motivation from
Dinitz?s conjecture on n x n matrices. Many questions have been asked and answered in
this subject. Many questions remain unasked and some questions, though innocent looking,
are still open. In this work, one will give some answers and ask some questions concerning
a fairly recent departure in the world of list-colorings.
To better understand the concepts, let us start with some elementary definitions in
graph theory. The reader should refer to [8].
For a start, all our graphs are assumed to be both finite and simple. Allow a possibility
for a graph G to be the empty graph on n vertices, if it has no edges; this is not to be
confused with the ?nothing graph? ? in which both the vertex and edge sets are empty.
A simple graph H = (V(H), E(H)) is called a subgraph of a graph G = (V(G), E(G))
if V(H)? V(G) and E(H)? E(G), where E is the edge set and V the vertex set.
H is a proper subgraph if at least one of the containments above is proper. A subgraph
H of graph G is called spanning subgraph whenever V(H) = V(G).
Let U ? V(G) and let E(U) denote the subset of E(G) of all edges with both ends in
U. Then H = (U, E(U)) is called the subgraph of G induced by U, denoted at times by
G[U]. In simple terms, an induced subgraph on a set of vertices U = {u1,u2,...,um} of a
graph G is the subgraph on vertex set U that contains every edge of G whose end points
are in U.
1
A graph can also be induced by an edge set, E ? E(G), in which case the vertex set
of the subgraph is just the set of ends of edges in E, with no additional vertices.
The line graph, L(G) of a graph G has the edges of G as its vertices; any two vertices
of of the line graph L (G) are adjacent if the edges in G to which they correspond have a
common vertex. Also, a graph H is said to be a line graph if there exists a graph G such
that H is isomorphic to L (G).
An independent set or a stable set of a graph G= (V , E) is a set of vertices I ? V in
G no two of which are adjacent.
A maximal independent set will be an independent set of vertices such that adding
another vertex of V into I will force an edge. Thus for a maximal independent set, any
vertex from G not in the set is adjacent to at least one vertex in the maximal set.
A maximum independent set is a largest independent set of G. It is the largest amongst
all the maximal independent sets. A clique in a graph is a set of pairwise adjacent vertices.
I will now turn your attention to the concepts of Graph Colorings in general and List
Colorings in particular.
A vertex coloring (or proper vertex coloring, when emphasis is necessary), for a simple
graph G= (V , E), is a function ? : V(G) ? C such that ?(u) negationslash= ?(v) whenever uv ? E(G),
where the collection C is a set of colors or symbols.
The independence number of a graph G is the maximum size of an independent set of
vertices.
A list assignment to a simple graph G is a function L : V(G) ? F,
where F is the collection of all finite subsets of C. By a proper L-coloring of G, I will
mean a function ? : V(G) ? C satisfying, for all u,v ? V,
2
i). ? (u)? L (u)
ii). if u,v is an edge of G, then ?(u)negationslash= ?(v) (i.e., ? is a proper vertex coloring of G ).
Condition (ii) is equivalent to the requirement that for each symbol? ? C, the ?support?
of ? with respect to ?, defined by
??1(?) = {v ? V|?(v) = ?}
is an independent set of vertices.
Example 1.1
The following graph has a proper L-coloring, where L is indicated in the picture. G can be
a0
a0
a0
a0
a0
a0
a0
a0
a0
a0a0a64a64
a64
a64
a64
a64
a64
a64
a64
a64a64{b,c}
{a,b}
{a,b}
{a,c}
Z W
X Y
circledot
circledot
circledot
circledot
G:
Figure 1.1: K4 - minus - an edge with assigned list
list colored as follows: ?(X)= b, ?(Y)= a, ?(Z)= c, ?(W)= a
The choice number of a graph G, denoted ch(G) is the smallest integer j such that
there is a proper L-coloring of G whenever |L (v)| greaterorequalslant j, for every vertex v ? V(G).
3
Since the chromatic number X(G) is defined similarly with the list assignment con-
strained to be constant, clearly X(G) lessorequalslant ch(G) for every G. If ch(G) lessorequalslant k I will some times
say that G is k? choosable, or k list colorable.
The hall number of a graph G is the smallest positive integer m such that whenever
each list has size greater or equal to m and HC is satisfied, a proper L-coloring of G exists.
The next graph is the graph K3,3 minus two independent edges, which is the smallest
graph whose choice number (the smallest list length that guarantees a proper coloring) is
greater than its chromatic number.
Example 1.2
{b,c}
{a,b}
{a,c}
{a,c}
{a,b}
{b,c}
ZW
X Y
U V
R
T
circledot
circledot
circledot
circledot circledot
circledot
G:
Figure 1.2: K3,3minus two independent edges with a list assignment with lists of length 2
from which no proper coloring is possible.
4
G is bipartite yet is not 2 list-colorable. Indeed, if vertex U is colored with color a, consider
the subgraph induced by the vertices {X,Y,U,V}= R, then the following coloring will
be forced: ?(X)= c and ?(V)= b. This leaves vertex Y not properly list colorable from
the given list because the only two colors on L(Y) have been taken up by its neighbors.
Similarly, if I let U to be colored with b and consider the subgraph induced by the vertices
{U,V,W,Z}= T, then the following coloring will also be forced: ?(W)= c and ?(V)= a.
Whence vertex Z can not be properly list colored from this list because the only two colors
on L(Z) have both been taken up by its neighbors. Thus this graph cannot be colored from
the given lists.
Theorem 1.1 P.Hall [12]
Suppose A1,A2,...,An are finite sets. There exist distinct representatives: a1,a2,...,an
such that ai ? Ai,i = 1,2,...,n, if and only if for each J ? {1,2,...,n}, |uniontextj?J Aj|greaterorequalslant|J|.
It was noticed in [14] that Hall?s theorem can be viewed as a theorem about list colorings
of cliques. Let V be the vertex set of the complete graph on n vertices, Kn, and let L be a
list assignment to V. Then because any two vertices of Kn are adjacent, a proper L-coloring
of Kn is a selection of distinct representatives from the sets L(v), v ? V, and vice versa.
Therefore, with V replacing the index set {1,2,...,n}, and with the sets L(v) replacing the
sets Ai, Hall?s theorem may be restated as follows:
Hall?s Theorem, restated: Suppose L is a list assignment to a complete graph K with
vertex set V. Then there is a proper L-coloring of K if and only if for each U ? V,
|
uniondisplay
u?U
L(u)|greaterorequalslant|U|.
5
This leads to the so called Hall?s Condition (HC) for the existence of a proper L-coloring
in an arbitrary finite simple graph G, to which L might be a list assignment.
Suppose that L is a list assignment to G and let H be a subgraph of G. Let ? be a
color in C. Denote by H? (or H(?,L)) the subgraph of H induced by the support set
{v ? V(H) | ? ? L(v)}.
Hall?s Condition is the following:
Hall?s Condition (HC) on G,L: For each subgraph H of graph G,
summationdisplay
??C
?(H?) greaterorequalslant |V(H)|, (1.1)
(where ? in equation (1.1) is the vertex independence number).
Remark 1.1
Since removing edges does not lower the vertex independence number ?, HC will be
satisfied if the inequality (1.1) holds for every induced subgraph H of G.
Hall?s Condition is a necessary condition for a proper L-coloring of G because in any
proper L-coloring of any subgraph H of G, ?(H(?,L)) is greater or equal to the number of
occurrences of ? in the coloring because the set of vertices on which ? appears in a proper
coloring is an independent set.
6
Remark 1.2
To show that a graph G and a list assignment L satisfy Hall?s Condition (HC), it suffices
to show that G?v is properly L-colorable for every vertex v ? V(G) and that the inequality
(1.1) in Hall?s condition holds for G itself.
Indeed, every induced subgraph H of G other than G itself is an induced subgraph
of G?v for some vertex v ? V(G). If G?v is properly L-colorable, then since HC is a
necessary condition for proper L-coloring, it must be that the inequality in HC holds for
every subgraph of G?v.
Remark 1.3
As a follow up of the restatement of Hall?s theorem, one should note that if U is a subset
of V(G), then the subgraph H of the complete graph K induced by U forms a clique. So
for each symbol ? ? C, ?(H(?,L)) = 1 if ? ? uniontextu?U L(u), otherwise it is zero. That is, as
a function of ?, ?(H(?,L)) is the characteristic function of ?u?UL(u). Consequently, (1.1)
becomes
|?u?U L(u)| =
summationdisplay
??C
?(H?) greaterorequalslant |V(H)| = |U|. (1.2)
Thus Hall?s Condition is equivalent to the condition in Hall?s theorem on the Systems
of Distinct Representatives (SDR) in the case of complete graphs. Therefore Hall?s theorem
can be restated: if K is a complete graph and L is a list assignment to K, then there is a
proper L-coloring of K if and only if K and L satisfy Hall?s Condition.
Example 1.3
Consider the four cycle, C4 with the given list assignment as shown below. First note
7
{b,c}
{a,b}
{c}
{a,c}
ZW
X Y
circledot
circledot
circledot
circledot
G:
Figure 1.3: Four Cycle
that graph G is not properly list colorable from the given list because once I color the vertex
Z with c, both Y and W are forced to be colored a and b respectively. This leaves vertex
X without any available colors since we require adjacent vertices to be colored differently.
To show that HC holds, note that for every vertex v ? V(G), the graph G?v is properly
list colorable from the lists (which implies the desired inequality for every proper induced
subgraph H of G) and ?(Ga) = ?(Gb) = 1, ?(Gc) = 2, hence the alpha sums equals the
order of G, 4. Thus Hall?s Condition is satisfied.
Theorem 1.2 Hilton and Johnson: [14] A graph G has the property that for all L, if
G, L satisfy Hall?s Condition then there is a proper L-coloring of G, if and only if every
block of G is a clique.
8
Recall that a block of a graph G is a subgraph maximal with respect to being connected
and containing no cut-vertex.
Lemma 1.1 Hall?s Condition holds for G and L if and only if the inequality in Hall?s
Condition (equation (1.1)) holds for each connected induced subgraph of G.
Cropper?s Problem
Let G = Kna50Kn ? the line graph of Kn,n , normally represented as an n x n array of
cells. Let some cells of G be filled in with symbols from the set Cn = {1,2,...,n}, so that
no symbol appears more than once in any row or column. So I have a partial latin square.
Let the list for an unfilled cell v(i,j) be defined in an obvious way as follows:
Cn - {symbols appearing in the filled cells in row i, column j}.
The list for a filled cell (of size one) will simply be the symbol in that cell.
Cropper posed the following question: is Hall?s Condition on such a graph G with such
a list assignment L sufficient for a proper L - coloring?
(Briefly, is Hall?s Condition on G and L sufficient for a completion of a partial latin
square?).
A theorem of Ryser?s answers in the affirmative Cropper?s question when the filled-in
parts of the partial latin square form a subrectangle.
Theorem 1.3 Ryser?s Theorem: [19]
An r?s latin rectangle R on n symbols ?1,?2,...,?n can be completed to a latin square
of order n if and only if
NR (?i) greaterorequalslant r+s?n for each i = 1,2,...,n, where NR (?i) is the number of occurrences
of the symbol ?i in R.
9
Theorem 1.4 Bobga, Hilton and Johnson: [2]
A latin rectangle on n symbols ?1,?2,...,?n can be completed to a latin square of order
n if and only if inequality (1.1) holds for H = G = Kna50Kn.
This statement turns out to be ?equivalent? to Ryser?s Theorem, in the sense that each
theorem is easily derivable from the other. As a corollary, when the filled-in parts form a
subrectangle, Hall?s Condition on G and L implies completability.
Theorem 1.5 Bobga and Johnson: [2]
If the filled-in part of a partial latin square form a subrectangle minus one cell, then
Hall?s Condition on G and L is sufficient for completion of the partial latin square.
A proof of theorem (1.5) and a variant of theorem(1.4) will be given in chapter 2.
Part of what I will try to do is to recast results by Andersen and Hilton [1], Buchanan
and Ferencak [3], Rodger [18], and Hoffman [17] in the form: when the filled-in parts belong
to a certain class of configurations, Hall?s Condition on G and L suffices for completion.
(This is not exactly right, as will be explained; Hoffman?s result is an exception). In all
the other cases so far, the theorems say that not only is Hall?s Condition on G and L
sufficient, but that only a few instances of the inequality in Hall?s Condition suffice for
proper L-coloring of G (i.e. for a completion).
Inspired by Cropper?s problem are the following concepts, whose application to Crop-
per?s problem have not yet been found but are of independent interest.
Let G and L satisfy Hall?s Condition and let H be a subgraph of G. One will say that
H is an L-tight subgraph of G if
summationdisplay
??C
?(H(?,L)) = |V(H)| (1.3)
10
If H is non-induced but is L-tight, then the subgraph generated by the vertices of H will
also be L-tight. If H is L-tight, then in every proper L-coloring of H, every color ? has
to appear ?(H(?,L)) times; i.e. a maximum independent subset of V(H?) is colored ? for
each ?.
The next set of definitions will consist of different modifications to Hall?s Condition on
G and L. They are actually stronger than Hall?s Condition for an arbitrary graph G and
list assignment L. However, when the underlining graph is complete, then they all coincide;
each is equivalent to the existence of a proper L-coloring of the graph. Each definition
demands first that Hall?s Condition on G and L be satisfied (although this is not explicit
in the case of HC*, below).
A simple graph G is said to satisfy Hall?s Condition plus on G and L, denoted
HC+, if
(i) G and L satisfy HC, and
(ii) there is an indexed family [S? : ? ? C] of independent subsets of V(G) satisfying:
(a) S? lies in V(G(?,L)) for all ? ? C (i.e., for all vertices v ? S?, ? ? L(v))
(b) for each L-tight subgraph H of G, |S?intersectiontextV(H)| = ? (H(?,L)).
I shall call such a family [S? : ? ? C] an HC+ satisfying family.
A simple graph G is said to satisfy Hall?s Condition plus plus on G and L, denoted
HC++, if G and L satisfy HC+, and in some HC+ satisfying family [S? : ? ? C] of
independent subsets of V(G), the S??s are pairwise disjoint. (That is, S?intersectiontextS? = ? for
? negationslash= ?).
If ? is a proper L-coloring of G, then the supports of ? ? C,
S? = ??1(?) = {v ? V|?(v) = ?}, ? ? C (1.4)
11
form an HC++ satisfying family for G and L.
So HC++ (and hence HC+) is a necessary condition for a proper L-coloring of G.
The next definition is due to Jeno Lehel. It deals with the conditional independence
number of a graph relative to a subgraph.
For an induced subgraph H of G, the conditional independence number of graph G
with respect to H, denoted ?(G|H), is the maximum cardinality of an independent set I of
V(G) such that |IintersectiontextV(H)| = ?(H).
This says that ?(G|?) = ?(G), where ? is the ?NOTHING? graph.
A simple graph G with list assignment L is said to satisfy Hall?s Condition star ,
denoted HC*, if
summationdisplay
??C
?(H?|T?) greaterorequalslant |V(H)|, (1.5)
holds for every induced subgraph H of G and every induced L-tight subgraph T of H.
Consider the ?NOTHING? graph ? to be an L-tight subgraph of any induced subgraph
H of G, and ?? = ? for each ? ? C.
Therefore if a simple graph G and list assignment L satisfy HC*, then they satisfy
Halls Condition.
A simple graph G with list assignment L is said to satisfy Hall?s Condition star star
(denoted HC**) if
summationdisplay
??C
min
TtriangleleftH
?(H?|T?) greaterorequalslant |V(H)|, (1.6)
holds for every induced subgraph H of G, where the minimum is taken over all L-tight
induced subgraphs T of H.
12
Because ? is allowed as an induced tight subgraph of every graph for any list assignment,
we clearly have HC** =? HC* =? HC.
Certainly, since HC is a part of or implied by the requirements for HC? for ? ?
{+,++,?,??}, it must be that each HC? =? HC for ? ? {+,++,?,??}.
I will now show that HC** is a necessary condition for the existence of a proper
L-coloring of a graph G.
Theorem 1.6 HC** is a necessary condition for the existence of a proper L-coloring of
a graph G.
Proof: Suppose there exists such a proper L-coloring ? of a graph G; we show that
HC** holds. Let H be an induced subgraph of G, I will show that the inequality in equation
(1.6) holds.
Suppose T is an L-tight induced subgraph of H and suppose ? ? C. Then
summationdisplay
??C
?(T?) = |V(T)|, (1.7)
and the number of times that ? appears as a color assigned by the function ? on T,
i.e., |??1(?)intersectiontextV(T)|, is actually ?(T?).
Therefore the number of times ? (for an arbitrary color ?) appears as a color in H
must satisfy the inequality
|??1(?)
intersectiondisplay
V(H)| lessorequalslant ?(H?|T?) (1.8)
because ??1(?)intersectiontextV(H) ? V(H?) is an independent set of vertices of H? which extends (by
T being L-tight), a maximum independent set of vertices of T?.
13
(Recall that the vertices in ??1(?)intersectiontextV(H) have ? on their L list and ?(H?|T?) is the
conditional independence number).
Since inequality (1.8) holds for every L-tight induced subgraph T of H, it must be that
|??1(?)
intersectiondisplay
V(H)| lessorequalslant min
TtriangleleftH
?(H?|T?) (1.9)
=?
summationdisplay
??C
|??1(?)
intersectiondisplay
V(H)| lessorequalslant
summationdisplay
??C
min
TtriangleleftH
?(H?|T?) (1.10)
=?
summationdisplay
??C
|V(H)| lessorequalslant
summationdisplay
??C
min
TtriangleleftH
?(H?|T?) (1.11)
which establishes the inequality (1.6) and hence the claim of the theorem.
a50
G is a Hall graph if whenever G, L satisfy HC, then there is a proper L-coloring of G.
Theorem 1.7 Hilton and Johnson: [14] G is Hall if and only if every block of G is a
clique.
(This is just a restatement of theorem 1.2).
Definition 1.1 G is a Hall+ graph if whenever G, L satisfy HC+, there is a proper
L-coloring of G.
Definition 1.2 G is a Hall++ graph if whenever G, L satisfy HC++, there is a proper
L-coloring of G.
Definition 1.3 G is a Hall* graph if whenever G, L satisfy HC*, there is a proper L-
coloring of G.
14
Definition 1.4 Finally, G is a Hall** graph if whenever G, L satisfy HC**, there is a
proper L-coloring of G.
I shall investigate these graph properties with a view to finding analogues of theorem
1.7, and possibly connections between the properties, but it is early days in this area. I
shall, for example, prove that all cycles are Hall+. Also, it will be shown that if a clique
were to be attached to a Hall? graph at a cut-vertex, then the resulting graph will still
belong to Hall?. This result holds for all ? ? { empty string, +, ++, *, ** }.
As to what happens when one joins two Hall? graphs with a cut-edge and whether or
not cycles were Hall* remain unanswered.
Lemma 1.2 Suppose that L is a list assignment to G, ? ? C and ?L is obtained from L by
replacing ? in the lists on each component of G(?,L) by a new color, for that component,
that does not appear in uniontextL(v), where the union is taken over all v ? V(G).
Then:
(a) G and L satisfy HC ?? G and ?L satisfy HC;
(b) G and L satisfy HC+ ?? G and ?L satisfy HC+;
(c) G and L satisfy HC++ ?? G and ?L satisfy HC++;
(d) G and L satisfy HC* ?? G and ?L satisfy HC*;
(e) G and L satisfy HC** ?? G and ?L satisfy HC**;
(f) There is a proper L-coloring of G ?? there is a proper ?L-coloring of G.
Proof: Parts (a), (b), (c), (d) and (e) depart from the observation that the indepen-
dence number of any graph is the sum of the independence numbers of its components.
From this it follows that if Hall?s Condition is satisfied, then a subgraph is tight if and only
15
if each component of it is tight, and also T is L-tight if and only if it is ?L-tight. From there
the arguments become quite laborious but straight forward, and I will omit them.
The proof of part (f) is as follows:
If there exists a proper L-coloring of G, then replace each occurrence of ? with its
replacement on the vertex?s list in the formation of ?L. This will also be a proper ?L-coloring
of G.
Conversely, if there is a proper ?L-coloring of G, we proceed as above and replace each
color ?-clone by ?.
square
Corollary 1.1 G ? Hall ?, where ? ? { empty string, +, ++, *, ** } ?? G is L-
colorable for every L satisfying HC ? with G and such that for each color ? ? C, G(?,L)
is connected.
Proof:
The forward part is clear by definition.
Conversely, suppose G satisfies the proposed less stringent requirement. Suppose L is a
list assignment for G that satisfies HC ? but for some colors, the support is not connected.
Then for one of those colors, one can modify L to ?L1 and if there is another different bad
color, one can repeat the procedure on ?L1 and get a new list say ?L2. This procedure can
be repeated as necessary. One then ends up with a new list assignment ?L of the desired
properties (i.e. every color has connected support). By assumption, G is ?L-colorable.
Therefore, by repeated application of the backwards implication in (f) of lemma 1.2, G is
L-colorable. Therefore G ? Hall ?.
square
16
Chapter 2
CROPPER?S PROBLEM AND RECASTED RESULTS
2.1 Introduction to Cropper?s Problem
The problem of completing a partial n by n latin square is a List Coloring Problem
in which the graph is the cartesian product of two n-cliques and the lists are determined
in an obvious way by the filled-in cells. Hall?s Condition (fairly well known) is a necessary
condition on a graph with a list assignment for the existence of a proper coloring. Matt
Cropper some years ago asked whether Hall?s Condition is sufficient for the completion of
a PLS. I will show in this chapter that the answer is a ?yes? when the filled-in cells form
-a sub-rectangle, or
-a sub-rectangle minus one cell.
In the former case, Hall?s Condition implies Ryser?s Condition.
A partial latin square of order n is an n x n array of n2 cells in which the cells may
contain either 0 or 1 symbols, the symbols all lying in a set Cn = {1,2,...,n} of n elements.
Furthermore, no symbol can occur in more than one cell in any row or column. If there are
no empty cells, then the partial latin square is a latin square.
Over the years there has been quite a considerable amount of interest in the question
of completing partial latin squares, ranging from, but not limited to, Ryser?s theorem [19],
Marshall Hall?s theorem [11], and the Evans? Conjecture [10], to the result of C. Colbourn
[5] that it is an NP ?complete problem to decide whether a partial latin square can be
completed.
17
Before delving into the results for this section, I will state the results mentioned above
due to their importance in the studies of latin square completions. Marshall Hall used
Phillip Hall?s theorem (theorem 1.1) on SDR to prove the following important theorem on
latin square completion.
Theorem 2.1 Marshall Hall, 1945 [11] Every r by n latin rectangle, 0 lessorequalslant r lessorequalslant n, on n
symbols, can be completed to a latin square of order n.
Proof: [7]
The cases r = 0 and r = n are both trivial. So it will be assumed that P is an r x n
latin rectangle, 0 < r < n. It will be shown that P can be extended to an (r +1) x n latin
rectangle, and hence ultimately to a latin square of order n.
For 0 lessorequalslant j lessorequalslant n, let Sj denote the set of all x ? {1,2,...,n} such that x does not occur
in the column j of P. Note that | Sj | = n?r, and since P is a latin rectangle each x ?
{1,2,...,n} belongs to exactly n?r of the sets S1,S2,...,Sn. It will be shown that there
exists a SDR ? s1,s2,...,sn? for the collection S1,S2,...,Sn and consequently that the
(r +1) x n latin rectangle P ?{(r +1,1,s1),(r +1,2,s2),...,(r +1,n,sn)} is an extension
of P.
Assume that such a System of Distinct Representatives does not exist. Then there exists
some k ?{1,2,...,n} and some choice of Sj1,Sj2,...,Sjk for which | Sj1?Sj2?...?Sjk |< k.
But then | Sj1 | + | Sj2 | +...+ | Sjk |= k(n?r) implies that there must exist some symbol
x ? {1,2,...,n} occurring in more than n?r of the sets Sj1,Sj2,...,Sjk. However this is
a contradiction as each x ? {1,2,...,n} belongs to exactly n?r of the sets S1,S2,...,Sn.
Hence a SDR must exist and so the r x n latin rectangle P can be extended to P ?{(r +
1,1,s1),(r+1,2,s2),...,(r+1,n,sn)}. If P ?{(r+1,1,s1),(r+1,2,s2),...,(r+1,n,sn)} is
18
a latin square of order n the argument is complete, otherwise the above process is repeated
and P ?{(r + 1,1,s1),(r + 1,2,s2),...,(r + 1,n,sn)} is extended to an (r + 2) x n latin
rectangle, and so on until a latin square is obtained. a50
The next two results are important in discussions relating to latin squares.
Conjecture 2.1 T.Evans? Conjecture, 1960 [10] Every partial latin square of order n
containing at most n?1 filled cells is completable.
The theorem of Ryser given in the introductory chapter is also important. Later in
this chapter, I shall restate it and use a lemma to establish it.
Theorem 2.2 Colbourn [5] Deciding whether a latin square can be completed is NP-
complete.
Example 2.1
1 3 4 8 2 {57} {56} {567}
4 2 1 3 8 {57} {56} {567}
5 6 3 1 7 {24}
7 5 2 4 6 {13}
6 7 8 2 5 {134}
{57} {57} 6 {123457}
{56} {56} 7 {123456}
{23} {14} {567} {567} {134} {123457} {123456} 8
Figure 2.1: An Incomplete PLS with some lists indicated
This PLS due to L. D. Anderson is incompletable and HC fails (and so it is not a
counter example to the conjecture that the answer in Cropper?s problem is yes!). Indeed,
19
look at the four cells (1,6),(1,7),(2,6),(2,7). Note that 6 and 7 can each be used exactly
once and so 5 must be used twice. Thus each of rows 1, 2, columns 6, 7 will have a 5 on
it. A careful look at cells (6,3), (6,4), (7,3), (7,4) indicate that 6 and 7 will each be used
exactly once, leaving the 5 to be used twice to complete the 4 cells. Hence each of rows 6,
7, columns 3, 4 will also have a 5. Thus in any attempted completion row 8 and column 8
cannot have a 5. However, to fill up the 8 cells in row 8, every number has to be used once.
Hence one cannot complete the PLS.
To see that HC fails, consider the subgraph H induced by all the preassigned cells
together with the cells:
(1,6), (1,7), (2,6), (2,7), (6,3), (6,4), (7,3), (7,4) and (i,8), (8,i) for i= 1,2,???,7.
Then| V(H) |= 50. Moreover, ?(H1)=5, ?(H2)=6, ?(H3)=5, ?(H4)=5, ?(H5)=8,
?(H6)=8, ?(H7)=8, ?(H8)=4.
=?
summationdisplay
??C
?(H?) = 49 < 50.
summationdisplay
??C
?(H?) < |V(H)|
means that the inequality in HC fails and so HC is not satisfied for G.
square
Remark 2.1
If the inequality for HC does not hold for some set of cells, it must also not hold for
the subset of that set of cells consisting of the empty, unprescribed, cells. This is because
adding a prescribed cell to a set of cells increases both sides of the inequality 1.1 by exactly
20
1. Thus we could simply have considered verifying HC only for the 22 cells within braces
(excluding the preassigned cells). The conclusion would have been the same.
2.2 Cropper?s Problem
Let G = KnsquareKn ? the line graph of Kn,n, normally represented as an n?n array of
cells.
Let some cells of G be filled in with symbols from the set {1,2,3,...,n} = Cn, with
the understanding that no symbol appears more than once in any row or column. So I have
a partial latin square. Below is an example with n = 7.
3 4 2
2 1
4
6
6 3
6 1 5
7 3 5
Figure 2.2: 7?7 partial latin square.
This one was provided to us by A. J. W. Hilton, and is an example due to Ron Aharoni,
the significance of which A. J. W. H. has now forgotten. But this particular one was thought
to possibly have great significance in the work on Cropper?s problem. It is not completable.
We did spend quite some time in studying this example with the hope of using it as a counter
21
example to the problem. However, it turned out that there is at least one ?bad? set of cells
(one that does not satisfies Hall?s Condition, see below) and so cannot serve as a counter
example. A. J. W. Hilton recently emailed us an example due to J. Goldwasser believed
to be a counter example to Cropper,s problem. If that were to be true, then Cropper?s
problem will be solved in the negative and the question will then become: when does HC
imply completability?
As stated in chapter 1, let the list for an unfilled cell v(i,j) be Cn\ {symbols appearing
in the filled cells in row i, column j}. The list for a filled cell (of size one) will simply be
the symbol in that cell. The list assignment corresponding to each cell in figure (2.2) is as
follows:
{1} {12} 7 3 5 {246} {1246}
{7} {237} {34} {24} 6 1 5
{157} 6 {45} {12457} {1247} {2457} 3
6 {12357} {345} {12457} {12347} {23457} {1247}
4 {12357} {356} {12567} {1237} {23567} {1267}
2 {357} 1 {4567} {347} {34567} {467}
3 4 2 {1567} {17} {567} {167}
Figure 2.3: A partial latin square with its accompanying list assignment.
To show that this cannot serve as a counter example to Cropper?s problem, I shall show
that there is a set of cells that satisfy the inequality in Hall?s condition. Such a set will be
referred to as a bad set. Note that any bad set remains bad if any of the preassigned cells
are added (or removed) from it. One such bad set is the following:
22
{1} {12} //// //// //// //// ////
{7} {237} {34} //// //// //// ////
//// //// {45} //// //// //// ////
//// {12357} {345} {12457} {12347} {23457} {1247}
//// {12357} {356} {12567} {1237} {23567} {1267}
//// {357} //// {4567} {347} {34567} {467}
//// //// //// {1567} {17} {567} {167}
Figure 2.4: Bad set indicated by the lists from figure (2.2).
Hall?s inequality is not satisfied because letting (?(i) stand for ?(Hi)), ?(1) = 4, ?(2) = 3,
?(3) = 4, ?(4) = 3, ?(5) = 4, ?(6) = 3, ?(7) = 5. Hence
7summationdisplay
?=1
?(?) = 26 < 27 = | V(H) | .
Theorem 2.3 The answer to the question in Cropper?s problem is ?yes? when the filled-in
cells form either
(i) a subrectangle, or
(ii) a subrectangle minus one cell.
We will see that the first case is ?equivalent? to Ryser?s theorem [19]: An r ?s latin
rectangle R on n symbols ?1,?2,...,?n can be extended to a latin square of order n if and
only if NR(?i) greaterorequalslant r+s?n for each i = 1,...,n, where NR(?i) is the number of occurrences
of the symbol ?i in rectangle R.
23
Proof:
First I show that HC implies completability for an n ? n partial latin square, when
the filled-in parts form a sub-rectangle. (The proof is due to Hilton, 1988 [13], but this
statement of what was proved is new). WOLOG, the filled-in sub-rectangle R is in the
upper left hand corner of the partial latin square. Let G = KnsquareKn consist of four portions
as in Figure 2.5, with the filled-in part R of dimension r?s as in Ryser?s theorem. Assume
HC holds.
For ? ? Cn, ?(G?) lessorequalslant ?(G) = n. Therefore, Hall?s Condition applied to the graph
G implies the following: n2 greaterorequalslant summationtext??Cn ?(G?) greaterorequalslant |V(G)| = n2, where the second inequality
results from HC with H = G.
Thus for each symbol ? ? Cn, ?(G?) = n. A maximum independent set of vertices
(cells) in G? must have a representative from every row and column, and therefore must
contain a total of r?NR(?) cells from A as well as s?NR(?) cells from B. Therefore, for
all ? ? Cn,
n = ?(G?) greaterorequalslant NR(?) +r?NR(?) +s?NR(?)
= r +s?NR(?).
Hence, NR(?) greaterorequalslant r +s?n. Whence, G is completable by Ryser?s theorem.
It is worth noting that in case (i), completability was implied by the inequality in
Hall?s condition for only one choice of H, namely, the whole graph. We shall see a similar
phenomenon in the proof for Case (ii).
Before proceeding to that case, I will give another proof of the sub-rectangle case,
not essentially different from the proof just given, but which will be convenient to refer to
24
A
B C
Rr
s
Figure 2.5: Rectangular blocks
later. This time, take H to be the copy of KrsquareKn represented by the first r rows of the
partial latin square. Since, for each i ? Cn, ?(Hi) lessorequalslant ?(H) = r, by the assumption that
HC is satisfied, |V(H)| = rn lessorequalslant summationtextni=1 ?(Hi) lessorequalslant rn; therefore, ?(Hi) = r for each i ? Cn.
Therefore a maximum independent set of cells in Hi must have a representative from each
of the r rows of H, and therefore i must occur on the lists of at least r ? NR(i) cells in
different columns, in the last n ?s columns of H. It follows that for each i ? {1,...,n},
r?NR(i) lessorequalslant n?s, which implies the condition in Ryser?s theorem and hence the claim (i).
Again the completability arises from the application of the inequality in Hall?s condition to
a single induced subgraph of the underlying graph G = KnsquareKn.
Now suppose that the filled-in parts of the partial latin square form a sub-rectangle
minus one cell. Permuting rows and columns, which amounts to merely renaming vertices
in the factors Kn of G = KnsquareKn, I can assume that the filled-in cells occupy Rprime, which is an
r?s rectangle in the upper left hand corner of the square, but with the (1,s) cell removed.
Let vij stand for the (i,j) cell, 1 lessorequalslant i, j lessorequalslant n, and let R = {vij | 1 lessorequalslant i lessorequalslant r,1 lessorequalslant j lessorequalslant s}, so
Rprime = R\{v1s}. Let L denote the list assignment induced by the filled-in cells.
25
First observe that L(v1s) negationslash= ?, for, if L(v1s) = ?, then taking H = {v1s} we would have
summationtext
??Cn ?(H(?,L)) = 0 < 1 = |V(H)|, contradicting the assumption that Hall?s condition is
satisfied. Next, I may as well suppose that for each ? ? L(v1s), the latin square cannot be
completed with ? in cell v1s. In view of the second proof of part (i) of the theorem, given
above, this means that if I fill v1s with ? and then define list assignment Lprime by
Lprime(v1k) = L(v1k)\{?},s < k lessorequalslant n,Lprime(v1s) = {?},Lprime(vis) = L(vis)\{?},r < i lessorequalslant n,
and Lprime = L otherwise (since ? ? L(v1s), ? does not appear in any of the filled cells
v2s,...,vrs), it must be that the inequality in Hall?s condition does not hold for Lprime and
the subgraph H = KrsquareKn of G induced by the vertices (cells) vij, 1 lessorequalslant i lessorequalslant r,1 lessorequalslant j lessorequalslant
n. That is, summationtext??Cn ?(H(?,Lprime)) < rn = |V(H)|. It must be, therefore, that for some
? ? Cn, ?(H(?,Lprime)) < r = ?(H). Since L satisfies Hall?s condition, by assumption, so
summationtext
i?Cn ?(H(i,L)) greaterorequalslant rn, so ?(H(i,L)) = r for all i ? Cn, and since, in H, L
prime differs from
L only on the cells v1s,v1,s+1,...,v1n, where Lprime(v1s) = {?} and Lprime(v1k) = L(v1k)\{?},
s < k lessorequalslant n, it must be that ? ? L(v1s).
The fact that ?(H(?,L)) = r means that there is a choice of r cells, one from each row
of H, no two in the same column, which have ? on their L-list. Since ? does not occur in the
filled-in cells in column s, below v1s, in H (and I know that it does not because ? ? L(v1s)),
I can let v1s be one of those r cells. It follows that ?(H(?,Lprime)) = r, so ? ? L(v1s)\{?}.
Further, it must be that for every choice of r independent cells from H bearing ? on their
L-list, v1s is the cell chosen from row 1. Consequently, letting Hprime = H ?v1s, I have that
?(Hprime(?,L)) = r?1.
Now, ? was an arbitrary element of L(v1s); letting ? now play the role just played by
?, we deduce the existence of ? ? L(v1s), ? negationslash= ?, such that ?(Hprime(?,L)) = r ? 1. Since
26
?(Hprime(i,L)) lessorequalslant ?(Hprime) = r for every i ? Cn, I have
summationtext
i?Cn ?(H
prime(i,L)) = ?(Hprime(?,L)) +?(Hprime(?,L)) +summationtext
i?Cn\{?,?} ?(H
prime(i,L))
lessorequalslant r?1 +r?1 +r(n?2)
= rn?2 < rn?1 = |V(Hprime)|,
contradicting the assumption that G and L satisfy Hall?s condition. So it must be that the
latin square can be completed by filling in v1s with a color from L(v1s) after all.
It is worth noting that while the completability in case (i) was implied by the inequality
in Hall?s condition for a single choice of H, either H = G or H = KrsquareKn, in case (ii)
the completability was implied by three instances of the inequality in Hall?s condition:
H = {v1s}, H = KrsquareKn, and H = KrsquareKn ?v1s. (In all of this, by KrsquareKn, we mean of
course a particular choice of KrsquareKn in G, the one constituted by the first r rows of the
array).
a50
2.3 Recasted Results
In this section, I will examine several theorems on completing PLS, as mentioned in the
introductory chapter, due to Buchanan and Ferencak [3], Andersen and Hilton [1], Rodger
[18] and a result of Hoffman [17] which deals with commutative latin squares. We shall
discover that each of them except Hoffman?s, possibly, can be restated in the form:
if the prescribed cells form such - and - such a configuration, then the satisfaction of the
inequality in Hall?s Condition for just a few special choices of induced subgraph(s) suffices
for the existence of a completion.
27
2.3.1 Recasting
Is HC sufficient for the completion of a partial latin square? Most think no!
What I have found: in 6 different theorems giving necessary and sufficient conditions
for a partial latin square of a certain sort (i.e. with the prescribed cells filling a certain
configuration) to be completable, not only do the theorems confirm that HC suffices in
those cases, but in each case, a small number of the 2n2 ? 1 inequalities constituting
HC suffices for completion.
I now present, in the form of a list, the re-casted results. I shall indicate the prescribed
cells and the H?s such that the inequality in HC for those H?s suffices for completability.
The proofs of the claims in 1 and 2 are given in section 2.2 above. The proofs of the
claims in parts 3,4,5 and 6 will use the well-known ancestor of Ryser?s Theorem, due to
Marshall Hall [11], theorem 2.1.
1. H.J. Ryser (1951 [19])
Prescribed cells or configuration: top left r?s sub-rectangle.
Cell set such that HC inequality implies completability: In section 2.2 it is shown that
either the full array of n2 cells, or the cells of the first r rows, are such that the HC inequality
(1.1) for the subgraph induced by those cells implies completability. There are numerous
other choices; for instance, the upper right r ?(n?s) sub-rectangle will do the job. This
can be inferred from the proof in section 2.2 and the fact that in the case of the graph and
list assignment involved in a partial latin square, if inequality (1.1) holds for some H then
it will also hold for any subgraph obtained from H by adding or deleting prescribed cells.
Thus the inequality (1.1) for the upper right r ? (n?s) sub-rectangle in a PLS in which
the prescribed cells occupy the upper left r ? s sub-rectangle implies inequality (1.1) for
28
H ? Kra50Kn, the first r rows, and by the proof of theorem 2.3 that implies that the PLS
is completable.
Here is a direct demonstration that (1.1) for H ? Kra50Kn?s, the upper right r?(n?s)
rectangle in a PLS with the cells of the upper left Kra50Ks prescribed, implies completability.
As in the proof of theorem 2.3, Ryser?s theorem will be the main engine of the proof.
Each i ? Cn appears on the lists of all the cells of r?NR(i) rows of H, and on no other
lists in H. (We appeal to the terminology in the proof of theorem 2.3). Therefore, Hi is
an (r ?NR(i))?(n?s) sub-rectangle of H, so ?(Hi) = min[(r ?NR(i)),(n?s)].
Therefore, assuming (1.1) holds for H, I have
|V(H)| = r(n?s) lessorequalslant
summationdisplay
i?Cn
?(Hi) lessorequalslant
summationdisplay
i?Cn
(r?NR(i))
=
summationdisplay
i?Cn
r?
summationdisplay
i?Cn
NR(i) = nr?rs = r(n?s).
Therefore, r ? NR(i) = min[(r ? NR(i)),(n ? s)] for each i ? Cn. Thus, for each i,
r?NR(i) lessorequalslant n?s, which implies completability, by Ryser?s theorem. a50
2. B. B. Bobga and P. D. Johnson (2007 [2])
Prescribed cells or configuration: the upper left r by s sub-rectangle minus one cell.
Without loss of generality, the missing cell will be v1,s in the first row and the sth column.
Cell sets or subgraphs induced by them such that HC inequality implies completability:
H ?
braceleftBig
{v1,s},Kra50Kn,(Kra50Kn)?v1,s
bracerightBig
, where Kra50Kn is in the first r rows.
See theorem 2.3 and its proof.
3. H.L. Buchanan and M. N. Ferencak (2000 [3])
Prescribed cells or configuration: first s rows together with the first d cells of row s+1.
29
Cell sets such that HC inequality implies completability:
The Hprimes here are precisely the 2(n?d)?1 subgraphs induced by the non-empty subsets
of the set of the last n?d cells in row s+ 1.
Proof:
What is to be proven is that the inequalities in Hall?s Condition for the described
choices of H suffice for the given PLS to have a completion.
By theorem 2.1, for completion, it suffices that the last n ? d cells in row s + 1 be
properly filled from their lists, so that the result is an (s+ 1)?n latin rectangle. Because
of the way the lists are formed, it therefore suffices that the clique on n?d vertices induced
by those n ? d cells be properly colorable from their lists. But then the original theorem
of Phillip Hall [12], reconstrued to be about list-colorings of cliques, says that 2(n?d) ? 1
inequalities constituting Hall?s condition in this case suffices for a completion.
a50
4. H.L. Buchanan and M. N. Ferencak (2000 [3])
Prescribed cells: top right s ? (n ? d) sub-rectangle together with the first d cells of
row s+ 1.
Cell sets such that HC inequality implies completability: The Hprimes here are precisely
the 2(n?d) ?1 sets referred to in 3 above together with the upper left s?d sub-rectangle.
Proof:
Buchanan and Ferencak prove in [3] that one can complete this PLS if and only if the
following three conditions are satisfied:
1. There are no collections X of columns and summationtext of symbols such that
(i) the d prescribed symbols in row s+ 1 lie in summationtext;
30
RHs
s+1 X
n-dd
Figure 2.6: Rectangular blocks with R and C filled-in
(ii) X is contained in the set of columns d+ 1 to n;
(iii) Every symbol ? in the set of all the symbols Cn \summationtext appears in each column in X
in the first s rows
(iv) |X| > |summationtext|?d.
2. Each symbol occurs (prescribed) at least s?d times in the first s rows.
3. No symbol occurring (prescribed) exactly s?d times in the first s rows also occurs in
the first d cells of row s+ 1.
Condition 1 above was given by Buchanan and Ferencak as necessary and sufficient for
completion in case 3, above, and it is easy to see why. If there existed a set X of columns
and a set summationtext? Cn satisfying (i)?(iv) under 1, just above, then the cells in row s+1 in the
columns of X would have their lists contained in summationtext\ {symbols in the first d cells of row
s+1}, so that |X| > |summationtext|?d constitutes a contradiction of one of the HC inequalities
associated with one of the 2(n?1) ?1 non-empty subsets of the last n?d cells in row s+1.
Therefore, if all of those inequalities hold, then there are no such X and summationtext, and the first
condition is satisfied.
31
Now let H be the subgraph of Kna50Kn consisting of the Ksa50Kd depicted in the upper
left of the array. For each symbol ? ? Cn, let N(?) be the number of appearances of ? in
the s?(n?d) rectangle R. Clearly, ? appears on the list of a cell in H if and only if the
cell is in one of the s?N(?) rows in which ? does not appear in R, and ? does not appear
as the prescribed entry of row s+ 1 in the column of the cell.
Therefore, H? is induced by the cells of a subrectangle of dimensions
(s?N(?))?d if ? negationslash? D = {symbols appearing in the first d cells of row s+1}, and of
dimensions (s?N(?))?(d?1) if ? ? D. Thus ?(H?) = min(s?N(?),d) if ? negationslash? D and
?(H?) = min(s?N(?),d?1) if ? ? D. Inequality (1.1) for H implies
sd = |V(H)|lessorequalslant
summationdisplay
??Cn
?(H?) lessorequalslant
summationdisplay
??Cn
(s?N(?)) = ns?
summationdisplay
??Cn
N(?) = ns?s(n?d) = sd. (2.1)
Since the ends of equation (2.1) are equal, the middles must also be equal. Hence all the
inequalities are equalities.
Hence s?N(?) lessorequalslant d if ? negationslash? D and s?N(?) lessorequalslant d?1 if ? ? D, which imply 2 and
3 above.
a50
5. L. D. Andersen and A. J. W. Hilton (1980 [1])
Prescribed cells or configuration: upper left r by s sub-rectangle, S, of a t by t array,
together with some or all of the cells (r + i,s + i), i = 1,2,...,t ? s, 0 < r < s < t; if
0 < r = s < t, the prescribed diagonal elements outside of R are in some or all of the
cells (r + i,s + i), i = 1,2,...,t ? s ? 1. [Taking into account the equivalences afforded
by simultaneous row and column permutations, the last requirement really says that if
32
0 < r = s < t, the prescription on the diagonal elements outside of R misses at least one
cell.]
Take H to be the r by (t?s) rectangle in the upper right of the array.
Proof:
For ? ? Ct, let NS(?) denote the number of occurrences of ? in S and let f?(?) denote the
squaresquare
? ?
? ?
squaresquare
HSr
t-r
t-ss
Figure 2.7: Rectangular blocks with S and local diagonals filled-in
number of occurrences of ? in the prescribed cells among those on the diagonal (r+i,s+i),
1 lessorequalslant i lessorequalslant t?s, if r < s, or 1 lessorequalslant i lessorequalslant t?s?1, if r = s.
Note that
summationdisplay
??Ct
f?(?) lessorequalslant
??
?
??
t?s?1, if r = s ;
t?s, if r < s .
Anderson and Hilton prove that the PLS with prescribed entries filling the rectangle S and
part of the diagonal outside of S, as described, can be completed to a Latin Square of order
t if and only if NS(?i) greaterorequalslant r +s?t+f?(?i) for each ? ? Ct.
For any symbol ? ? Ct, H? is induced by the cells in the (r?NS(?))?(t?s?f?(?))
subrectangle formed by the intersection of the r ?NS(?) rows, among the first r rows, in
which ? does not appear in that row in S, and the t?s?f?(?) columns, among the last t?s
33
columns, such that ? does not appear in that column in a prescribed cell on the diagonal
outside of S.
Therefore ?(H?) = min(r?NS(?),t?s?f?(?)) for each ?.
Then inequality (1.1) implies
r(t?s) = |V(H)| lessorequalslant summationtext??C ?(H?) lessorequalslant summationtext??C(r?NS(?))
= summationtext??C r ? summationtext??C NS(?) = tr?rs = r(t?s).
Ends equal means middles must also be equal. We conclude that for each ?,
r?NS(?) lessorequalslant t?s?f?(?) ?? NS(?) greaterorequalslant r +s?t+f?(?) as required.
a50
6. C. A. Rodger (1984 [18])
Prescribed cells or configuration: the top left n by n subrectangle, R of a t by t array,
t greaterorequalslant 2n+ 1, together with all the main diagonal elements, (i,i) for i = n+ 1,n+ 2,...,t.
square
? ?
? ?
D?
? ?
? square
HRn
t-n
t-nn
Figure 2.8: t?t square with block R and main diagonal D filled-in
For ? ? Ct, let NR(?) denote the number of occurrences of ? in R and let f(?) denote
the number of occurrences of ? on the diagonal outside of R, in the cells (i,j), n+1 lessorequalslant i lessorequalslant t.
34
Rodger proves that a PLS with such a prescription configuration can be completed to
a LS of order t if and only if: [Andersen and Hilton?s requirement in part 5 above]
(i) NR(?) greaterorequalslant 2n?t+f(?) for each ? ? Ct;
(ii) for each ? ? Ct, if NR(?) = n then f(?) negationslash= t?n?1; and
(iii) if R is a LS on the symbols ?1,?2,...,?n and t = 2n+ 1, then summationtextni=1 f(?i) negationslash= 1.
Consider V(H) = {v(i,j) : 1 lessorequalslant i lessorequalslant n, n < j lessorequalslant t}.
Then |V(H)| = n(t?n).
For this choice of H, the inequality in Hall?s Condition will imply condition (i) of this
theorem; the proof is just like that in item 5, above, but I give it any way.
As in 5, for each symbol ? ? Ct, H? is an (n?NR(?))?(t?n?f(?)) subrectangle of
H.
Then for each ? ? Ct,
?(H?) = min(t?n?f(?),n?NR(?)).
If the inequality in 1.1 holds for H, then
n(t?n) lessorequalslant
summationdisplay
??Ct
?(H?) =
summationdisplay
??Ct
min(t?n?f(?),n?NR(?))
lessorequalslant
summationdisplay
??Ct
(n?NR(?))
=
summationdisplay
??Ct
n ?
summationdisplay
??Ct
NR(?) = nt?n2 = n(t?n).
It then follows that min(t?n?f(?),n?NR(?)) = n?NR(?)) for each ?; hence
n?NR(?) lessorequalslant t?n?f(?) for each ?, which is condition (i).
35
Next I consider condition (ii). It is my claim that if the inequality (1.1) holds for each
H ? {column n+ 1, column n+ 2,..., column t}, then condition (ii) also holds.
Proof:
Suppose (ii) does not hold; then for some ?, NR(?) = n and f(?) = t?n?1. Then ?
appears at all but one place on D, the part of the main diagonal outside R. Let H be the
column of the cell on D where ? does not appear. Then ? appears on no list on H and H
is a clique, hence ?(H?) = 0 and ?(H?) lessorequalslant 1 for all ? ? Ct.
So
summationdisplay
??Ct
?(H?) lessorequalslant t?1 < t = |V(H)|.
This contradicts HC and so it must be that if HC holds, then condition (ii) holds.
Finally, consider condition (iii).
When t = 2n + 1, (iii) is guaranteed by the inequality (1.1) for the following choices
of H (notice there will be t?n of them in all):
H(k) = {v(i,j) : 1 lessorequalslant j lessorequalslant n, n+ 1 lessorequalslant i lessorequalslant t}?{v(i,j) : n+ 1 lessorequalslant i lessorequalslant t, 1 lessorequalslant j lessorequalslant n}
?{kth row}?{kth column}, for k = n+ 1,n+ 2,...,t.
you have vextendsinglevextendsingleV(H(k))vextendsinglevextendsingle = 2n(t?n) + 2(t?n) ? 1 = 2n(n+1) + 2n + 1
because t = 2n+1 ? t?n = n+1. I will show that if condition (iii) fails, then inequality
(1.1) for one of the H(k) will fail.
Suppose t = 2n + 1, and R is a latin square on the symbols ?1,?2,...,?n, but
summationtextn
i=1 f(?i) = 1. Then exactly one symbol ?i, i ? {1,2,...,n}, appears on D, and it
appears exactly once, say in the kth row and kth column as shown in figure 2.9 above.
Because R is a LS on ?1,?2,...,?n, for 1 lessorequalslant j lessorequalslant n, ?j does not appear on the list of
any cell v(i,j), n+ 1 lessorequalslant i lessorequalslant t, 1 lessorequalslant j lessorequalslant n or 1 lessorequalslant i lessorequalslant n, n+ 1 lessorequalslant j lessorequalslant t.
36
?i
R
A
Bn
t-n
t-n
k
k
n
Figure 2.9: t?t square with indicated H(k) filled-in
If j negationslash= i then ?j appears on the lists of the cells of row k in columns n+1,n+2,...,t,
except row k, and the same for column k, so ?(H?j) = 2. Clearly, ?(H?i) = 1. Letting
?n+1,...,?t denote the symbols in Ct \{?1,?2,...,?n}, for n + 1 lessorequalslant j lessorequalslant t it is easily seen
that H?j consists of a (t?n?f(?j))?n sub-rectangle of the lower left (t?n)?n rectangle
A, together with an n?(t?n?f(?j)) subrectangle of the upper right n?(t?n) rectangle
B, together with t?n?f(?j)?1 cells in each of row and column k, outside of A and B.
To see how to estimate ?(H?j) in this case, assume that k = n + 1 (which could be
actually achieved by permuting rows and columns, an isomorphism of the graph). Then
?(H?j) is contained in the union of two rectangles, one (n + 1?f(?j))?(n + 1) and the
other (n+ 1)?(n+ 1?f(?j)). (Since t = 2n+ 1,t?n = n+ 1).
Therefore
?(H?j) lessorequalslant 2min[n+1,n+1?f(?j)] = 2(n+1?f(?j)), for each j = n+1,...,2n+1.
But if f(?j) = 0, ?(H?j) lessorequalslant 2n + 1 = 2(n + 1 ? f(?j)) ? 1 , because it is not
possible to find 2n+2 independent cells in the union of A, B, row n+1 and column n+1.
37
And f(?j) = 0 for some j ? {n+ 1,...,2n+ 1}, because
2n+1summationdisplay
j=n+1
f(?j) = n+ 1?1 = n,
and there are n+ 1 values of j summed over.
Therefore,
2n+1summationdisplay
j=1
?(H?j) =
nsummationdisplay
j=1
?(H?j) +
2n+1summationdisplay
j=n+1
?(H?j)
lessorequalslant 2(n?1) + 1 + 2
2n+1summationdisplay
j=n+1
[(n+ 1)?f(?j)]?1
= 2n?1 + 2(n+ 1)2 ?2
2n+1summationdisplay
j=n+1
f(?j)?1
= 2n?1 + 2(n2 + 2n+ 1)?2n?1
= 2n2 + 4n < 2n2 + 4n+ 1 =
vextendsinglevextendsingle
vextendsingleV(H(k))
vextendsinglevextendsingle
vextendsingle
Thus summationtexttj=1 ?(H(k)?j ) < vextendsinglevextendsingleV(H(k))vextendsinglevextendsingle which contradicts HC.
Thus for this choice of H(k), Hall?s Condition fails. By contraposition, one can then
conclude that if HC holds, then so also will condition (iii).
a50
38
There is one other result related to Cropper?s Problem that I wish to inspect.
7. D. G. Hoffman (1983 [17])
This theorem gives two necessary and sufficient conditions for a partial (incomplete)
commutative LS to be completable to a commutative LS. One is equivalent to the satisfac-
tion of an HC inequality for a choice of one H, but the other does not seem to arise from
any combination of the inequalities in HC.
Referring to figure 2.10, let c(i) be the number of appearances of the symbol i in all of
A, d(i) be the number of occurrences of the symbol i on the main diagonal of A, and t(i)
be the number of appearances of the symbol i along the tail of A. We have the following
theorem by Hoffman:
Theorem 2.4 D.G. Hoffman 1983:([17]) Let A be a commutative incomplete latin
square of size r and order n, with content c and diagonal d. Let t : N ?N, with
summationtext
i?N t(i) = n?r. Then A can be embedded in a commutative latin square B with tail t if
and only if, for each i ? N, (1). d(i) + t(i) ? n(mod 2), and (2). 2r + t(i) lessorequalslant n + c(i).
Since this theorem is about completing partial commutative latin squares, it would
not finish off Cropper?s Problem if it turned out that Hall?s Condition is not sufficient for
completability in such circumstances, but such an example would bear on a more general
question:
which graphs G have the property that for every partial proper L-coloring of G with
X(G) colors, {1,2,...,X(G)}, there is an extension to a proper coloring of G with X(G)
colors whenever G and the list assignment L defined by the partial coloring in the obvious
way, (for an uncolored vertex v, I have: L(v) = {1,2,...,X(G)}-{colors on N(v)}) satisfy
Hall?s Condition?
39
I will now show that the second condition of Hoffman?s result is equivalent to HC for
some prescribed set of vertices.
Proof:
square
? ?
? ?
t(i)?
? ?
? square
HAr
n-r
n-rr
Figure 2.10: n?n commutative square with block A and main diagonal filled-in
Referring to figure 2.10, given A and its tail (main diagonal outside A) prescribed, let
H be defined by
V(H) = {Vij : 1 lessorequalslant i lessorequalslant r, r + 1 lessorequalslant j lessorequalslant n}
I claim that the inequality in HC for this H will imply condition (2) : 2r+t(i) lessorequalslant n+c(i)
for each symbol i = 1,2,...,n.
For each symbol i, we see that i appears on the lists in cells of r?c(i) rows of H where
they intersect n?r?t(i) columns.
So H(i,L) ? Hi is an (r?c(i))?(n?r?t(i)) rectangle.
=? ?(Hi) = min(r?c(i),n?r?t(i)) and so by HC, I have
|V(H)| = r(n?r) lessorequalslant
nsummationdisplay
i=1
?(Hi) =
nsummationdisplay
i=1
min[r?c(i),n?r?t(i)]
40
lessorequalslant
nsummationdisplay
i=1
(r?c(i)) = nr ?
nsummationdisplay
i=1
c(i) = nr?r2 = r(n?r) = |V(H)|.
Since the ends are equal, it must be that all the inequalities between were actually
equalities. By termwise equality, it means that min(r?c(i),n?r?t(i))= (r?c(i) and so it
must be that r?c(i) lessorequalslant n?r?t(i)) for all symbol i = 1,2,...,n. Thus (2) : 2r+t(i) lessorequalslant n+c(i)
for each symbol i is satisfied if the inequality for HC is satisfied for this choice of H.
a50
The problem of completing a partial commutative latin square to a commutative latin
square is indeed a list-coloring problem in the same way that completing a partial latin
square to a latin square is, but the underlying graph is not Kna50Kn, nor are the lists gener-
ated from the prescribed cells just as they are in the P.L.S case. However, the underlying
graph in partial commutative latin square case is obtainable from Kna50Kn by adding edges,
and therefore the lists dictated by a partial prescription are subsets of the lists dictated
in Kna50Kn by the same prescription. Therefore, HC in the true partial commutative latin
square case implies HC in the Kna50Kn, or P.L.S., setting. Therefore, the preceding shows
that HC in the true partial commutative latin square case implies condition (2) in Hoffman?s
theorem. we doubt that it implies (1), which does not seem the sort of thing that could be
implied by a collection of inequalities, but the matter requires further investigation.
2.3.2 Hoffman?s Lemma
I will state and proof a result that will enable us give another proof of Ryser?s theorem.
This result is due to D.G Hoffman.
Lemma 2.1 Hoffman?s Lemma: Let G = KmsquareKn ? the line graph of Km,n be an m by
n rectangular array of cells such that each cell holds exactly one symbol.
41
Then one can permute within the rows (columns) to make the array G to become column
latin (respectively row latin) if and only if no symbol appears more than n times (respectively,
m times) in the m by n array.
G can be rearranged by permutations within lines to be both row and column latin if
and only if no symbol appears more than min(m,n) times.
Before giving a proof of this lemma, I will first give a remark, an example of the use of
the lemma, a corollary and a result of K?onig.
By the pigeon hole principle,we remark that if there were n + 1 (respectively m + 1)
copies of a symbol ? in the m by n array G, then two of them will be forced to appear on
the same column (respectively, row). This will contradict latinness.
An application of this lemma is the following example.
Example 2.2
2 2 1 3 4 7
1 2 3 4 5 6
2 3 4 5 6 7
1 1 2 4 3 3
2 4 6 8 8 8
Figure 2.11: Randomly filled-in 5 ? 6
Since each symbol appears not more than n = 6 times, one can make the array to be
column latin by permuting within each row.
42
2 2 1 3 4 7
6 3 2 4 5 1
3 4 5 6 7 2
1 1 4 2 3 3
4 6 8 8 2 8
Figure 2.12: Column latin 5 ? 6
However, there are more than m = 5 copies of the symbol 2. Hence the table cannot be
made row latin because one cannot place 6 copies of 2 in exactly 5 rows without duplicating
in some row.
If we modify this table to a new table in which no symbol appears more than 5 =
min(5,6) times in the whole array, we see by Hoffman?s Lemma that the new array can be
made to become a latin rectangle as shown in our next example.
Example 2.3
Consider the array given by
1 2 1 3 4 7
1 2 3 4 5 6
2 3 4 5 6 7
1 1 2 4 3 3
2 4 6 8 8 8
Figure 2.13: Randomly filled-in 5 ? 6 Rectangle
43
By permuting within the rows, I get the following array which is column latin
2 7 1 3 1 4
6 3 2 4 5 1
3 4 5 6 7 2
1 1 4 2 3 3
4 6 8 8 2 8
2 7 8 3 1 4
6 3 2 4 5 1
3 4 1 6 7 2
1 6 4 2 3 8
4 1 5 8 2 3
Figure 2.14: 5 ? 6 Latin Rectangle
The final latin rectangle results from permutations within the columns.
Theorem 2.5 K?onig 1916:[8] If G is a bipartite multigraph with chromatic index Xprime(G)
and maximum degree triangle(G), then Xprime(G) = triangle(G).
Proof of Hoffman?s Lemma:
The ?only if? claim has been proven already.
Suppose each symbol appears no more than n times in the array. I aim to show that
one can permute within the rows to make the array column latin. Make a bipartite graph
as follows.
Each row has n entries, so n symbols appear in each row. Hence I get deg(ri) = n,
i = 1,2,...,m. deg(sj) = number of appearances of symbol sj in array, for j = 1,2,...,k.
But each symbol appears no more than n times by hypothesis. Hence deg(sj) lessorequalslant n, for
j = 1,2,...,k.
44
?
?
?
?
?
?
?
c(t)
(?)?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
r1
r2
r3
r4
ri
rm
s1
s2
s3
s4
sj
sk
Symbols in arrayRows in array
where (?) stands for as many edges as appearances of symbol sj in row ri.
Figure 2.15: Rows ri and symbols sj in the array.
By theorem 2.5, Xprime(G) = triangle(G) = n as G is a bipartite multigraph. So I can properly
color the edges of this bipartite graph with n colors: c1,c2 ...cn which in turn represent the
columns.
Now whenever an edge from row ri to symbol sj is colored ct, put one of the sj?s in row
i in column t. Since the coloring is proper, only one symbol will appear in row i, column
t after this arrangement and, by the way the bipartite graph is defined, each row will still
contain the same numbers of the different symbols that it did before. That is, there has
been rearrangement only within each row.
a50
2.3.3 Another look at Ryser?s Theorem
I now present another proof of the theorem of Ryser?s, a result that has been the
backbone of the section on recasted results.
45
Theorem 2.6 Ryser?s Theorem: [19]
An r?s latin rectangle R on n symbols ?1,?2,...,?n can be completed to a latin square
of order n if and only if NR (?i) greaterorequalslant r +s?n for each i = 1,2,...,n,
where NR (?i) is the number of occurrences of the symbol ?i in R.
Proof: I need to complete the partial latin rectangle R to an r by n latin rectangle
on ?1,?2,...,?n. By an old result of M.Hall, (Theorem 2.1) which can also be proved
using Hoffman?s Lemma 2.1, any r by n latin rectangle on n symbols can be completed
to a latin square. Complete each row to be of length n so that each row contains all n
symbols ?1,?2,...,?n. One can then complete to an r by n latin rectangle if and only if
one can rearrange within the rows of the r by n ? s block made by the first r rows, last
n?s columns, so that the result is (also) column latin. By Hoffman?s Lemma 2.1, one can
do this rearrangement if and only if for each i = 1,2,...,n,, ?i appears at most n?s times
in the array.
But ?i appears in each row, so in all, it appears r times in the r by n array. In R, ?i
appears NR(?i) times and so in the r by n?s block, it appears r?NR(?i) times. In the r
by n?s block, the primenprime in Hoffman?s Lemma is the number of columns, n?s. Thus
the completion to an r?n latin rectangle is possible if and only if
r?NR(?i) lessorequalslant n?s ?? NR (?i) greaterorequalslant r +s?n, where n?s is the number of times
the symbol ?i appears in the r by n?s rectangle.
a50
46
Chapter 3
HALL+ AND HALL++ GRAPHS
3.1 Introduction
In this chapter, I shall explore the relations that exist betweenHALL+andHALL++
graphs and attempt answers to questions about obtaining new HALL+ and HALL++
graphs from old ones. I shall also look at a few graph theoretic operations that either
preserve or modify the property of a graph being HALL+ or HALL++.
The main result of this chapter is that the operation of attaching cliques to vertices
of HALL+ graphs yield a HALL+ graph, and the same for HALL++. I shall also
prove any induced subgraph of a HALL+ graph is HALL+, and the same holds for
HALL++. Hence the classes of HALL+ and HALL++ graphs have forbidden subgraph
characterizations.
3.2 Inclusion Property
I shall now try to build up a theory for HALL+ graphs that resembles that for HALL
graphs.
Recall that a simple graph G ? HALL+ if and only if for every list assignment L of
G, if G and L satisfy HC+, then there is a proper L-coloring of G.
Theorem 3.1 If G ? HALL, then G ? HALL+ and the converse is false. Thus HALL
subsetnoteql HALL+ ? HALL++.
47
Proof:
G ? HALL means whenever G and L satisfy HC, then there is a proper L-coloring
of G. Now suppose HC+ is satisfied for G and L. I wish to show that a proper L-coloring
for G exists. Since HC+ is satisfied, it follows that HC also holds for G and L. Hence
G ? HALL =? there is a proper L-coloring for G. The same logic works for HALL+ ?
HALL++ because if G and L satisfy HC++, then G and L satisfy HC+ and so there
is a proper L-coloring of G as G ? HALL+. Hence G ? HALL++.
To complete the proof, I will give an example of a graph which is HALL+ but not
HALL. Consider G = C4. Then by a later result, proposition 3.3, G is HALL+. However,
by the characterization of Hall graphs in theorem 1.7, I know that C4 is not HALL.
a50
Lemma 3.1 Let H be an induced subgraph of G with list assignment L. Suppose that H and
L satisfy HC+. Let tildewideL be an extension of L to V(G) such that G and ? satisfy HC and any
tildewideL-tight subgraph of G is also an L-tight subgraph of H. Then any HC+ - satisfying family
[S? : ? ? C] for H and L is also an HC+ - satisfying family for G and tildewideL; in particular, G
and tildewideL satisfy HC+.
Proof:
Since S? ? V(H(?,L )) ? V(G(?,L) for each symbol ? ? C, we see that S? must
belong to V(G(?,L).
By assumption, any tildewideL-tight subgraph T of G is also an L-tight subgraph of H. So
?? ? C, T(?, tildewideL) = T(?,L) and so I can conclude that |S?intersectiontextV(T)| = ? (T(?,L)) = ?
(T(?, tildewideL)).
a50
48
Proposition 3.1 If G ? HALL+, (respectively HALL++) and H is an induced subgraph
of G, then H ? HALL+ (respectively HALL++).
Proof:
I will do the proof for HALL+ only. The proof for HALL++ is very similar.
Let G ? HALL+. Then by definition, if G and L satisfy HC+, then there is a proper
L-coloring. Now take H induced in G as postulated and suppose that L is a list assignment
to H such that H and L satisfy HC+. The proof will be complete once I can show that
there is an L-coloring for H. Extend L to a list assignment tildewideL of G by assigning huge lists
to the part of G outside of H, i.e. to the vertices in V(G)\V(H), huge enough so that G
and tildewideL satisfy HC and any tildewideL-tight subgraph T of G will also be an L-tight subgraph of H.
Then by the result above, lemma 3.1, whatever the HC+-satisfying family [S? : ? ? C] was
for H and L, it is also an HC+-satisfying family for G and tildewideL. Therefore G has a proper
tildewideL-coloring, and therefore H has a proper L-coloring. a50
Example 3.1
a0
a0
a0
a0
a0
a0
a0
a0
a0
a0a0a64a64
a64
a64
a64
a64
a64
a64
a64
a64a64a64a64
a64
a64
a64
a64
a64
a64
a64
a64a64 a0a0
a0
a0
a0
a0
a0
a0
a0
a0a0 a8a8a8
a8a8
a8a8
a8a8
a8a8
a72a72
a72a72
a72a72
a72a72
a72a72a72
a72a72
a72a72
a72a72
a72a72
a72a72a72
a8a8
a8a8
a8a8
a8a8
a8a8a8
a24a24a24a24
a24a24a24a24
a24a24a24
a90a90
a90a90
a90a90
a90a90
a90a90
a90
a88a88a88a88
a88a88a88a88
a88a88a88
a26a26
a26a26
a26a26
a26a26
a26a26
a26
a88a88a88a88
a88a88a88a88
a88a88a88
a26a26
a26a26
a26a26
a26a26
a26a26
a26
a24a24a24a24
a24a24a24a24
a24a24a24
a90a90
a90a90
a90a90
a90a90
a90a90
a90
{a,b,c,d,e}
{a,b,c,d,e}
{a,b}
{a,c}
{a,d}
{a,e}
{b,c}
{b,d}
{b,e}
{c,d}
{c,e}
{d,e}
circledot
circledot
circledot
circledot
circledot
circledot
circledot
circledot
circledot
circledot
circledot
circledot
Figure 3.1: G = K2 V K10 with assigned list.
49
This example is due to Matt Cropper.
The graph G has no tight subgraphs and one cannot properly color. However, deleting
any vertex leaves a properly L-colorable graph. One can therefore check HC for G alone.
Since ?(G?) = 4 for each symbol, we see that summationtext??C ?(G?) = 20 > 12 = |V(G)|,
and so HC is satisfied. Since there are no tight subgraphs, one can take S? = ?,??. Then
[S?;? ? C] is an HC++ - satisfying family.
Conclude that G negationslash? Hall? for ? ? { empty string, +, ++, *, **}.
3.3 Forbidden Induced Subgraph Characterization
Let P be a property of graphs (such as being a Hall?, where ? ? { empty string, +,
++, *, ** }).
Definition 3.1 I will say that P has a forbidden induced subgraph characterization if and
only if there is a collection Q of graphs such that a graph G has property P if and only if
G has no induced subgraph in the set Q.
In general, to see that a property P has an induced subgraph characterization, we check
whether or not property P is closed under the property of taking induced subgraphs.
Proposition 3.2 A property P of graphs (which some graphs actually have) has a forbidden
induced subgraph characterization if and only if the collection G(P) of graphs, defined by
G(P) = {G: G has property P} is closed under the operation of taking induced subgraphs.
Proof: The ?only if? part is true because if I is an induced subgraph of an induced
subgraph H of G, then I is also induced in G. Thus the collection is closed under taking
induced subgraphs, if P has forbidden induced subgraph characterization, for if G can
contain no induced subgraph belonging to Q, then neither can H.
50
To see that the other implication is also true, suppose that G(P) is closed under taking
induced subgraphs and define the collection Q to be:
Q = {H | H is a graph that does not have property P, but ? v ? V(H), H ?v ? G(P) }.
I will show that property P has a forbidden induced subgraph characterization, with
Q as the collection of forbidden induced subgraphs, whenever G(P) is closed under the
operation of taking induced subgraphs.
If the graph G has an induced subgraph H ? Q, then by hypothesis, G does not have
property P because G has an induced subgraph without property P. Suppose that G does
not have property P . I want to see that G has an induced subgraph in Q. If G ? v has
property P for every vertex v ? V(G), then G itself is in Q and we are done. Otherwise,
G1 = G?v1 does not have property P, for some v1 ? V(G). If G1 ?v has property P for
every v ? V(G1) then G1 ? Q and we are done. Otherwise, for some v2 ? V(G1), G1 ?v2
= G?v1 ?v2 does not have property P.
Continuing in this way, we have a sequence G1,G2,... of graphs, Gk = Gk?1 ?vk for
some vk ? V(Gk?1), each without property P. The sequence much terminate at some graph
H = Gk, an induced subgraph of G with at least two vertices which does not have property
P but such that H?v does have property P for every v ? V(H); i.e., H ?Q. H must have
at least two vertices because by assumption G(P) is non-empty and closed under taking
induced subgraphs, so K1 has property P.
a50
Of course, forbidden subgraphs exist, however, completely characterizing the minimal
set Q, can be a little more involving. This is left for further research.
51
Corollary 3.1 [6] The class of Hall? graphs, for ? ? { empty string, +, ++, *, ** } has
a forbidden induced subgraph characterization.
This result says that if P is the property of being Hall, then there is a collection Q of
graphs such that a graph G is Hall if and only if G has no induced subgraph in the set Q.
Following is a characterization of HALL graphs. I do not yet have forbidden induced
subgraph characterizations for HALL+ and HALL++, and I do not know if the HALL*
or HALL** graphs have such a characterization.
For a start, let us restate the following equivalent results of Hilton and Johnson [15].
Theorem 3.2 [15] G ? Hall if and only if G has no induced Cn,n greaterorequalslant 4 nor K4 -minus-
an-edge.
Question : What characterization similar to theorem 3.2 above can be stated for the
class of HALL+, HALL++ as well as HALL* and HALL** graphs?
3.4 Closure Property
We now have enough background knowledge of HALL+ graphs to tackle one of the
main results in this work.
Theorem 3.3 If a graph H ? Hall+, and a graph G is obtained from H by attaching a
clique to an arbitrary vertex v of H, then G ? HALL+. Thus the class of HALL+ graphs
is closed under attachment of cliques.
Lemma 3.2 Suppose K is a clique, L a list assignment to the graph K, and K and L
satisfy Hall?s Condition. Suppose further that H1,H2 are L-tight sub-cliques of K. Then
1). H0 = H1 ?H2 is also L-tight.
52
2). H3 = < H1 ?H2 > is also L-tight.
It is clear that both H0 and H3 are cliques.
Proof of Lemma:
Since H3 is a clique, ?(H3(?,L)) as a function of the symbol ? is the characteristic
function of uniontextv?V (H3)L(v). This is true since the ? value will either be 1 or 0 depending on
whether or not ? ? ?L(v). That is,
?(H3(?,L)) =
??
?
??
1, if ? ? uniontextv?V (H3)L(v);
0, otherwise.
By Hall?s Condition on H3 and L, and the fact that
V(H3) = V(H1)?V(H2), you have the following:
summationdisplay
??C
?(H3(?,L)) greaterorequalslant |V(H3)| = |V(H1)?V(H2)|. (3.1)
Also, ?(H3(?,L)) being a characteristic function
? summationtext??C ?(H3(?,L)) =
vextendsinglevextendsingle
vextendsingleuniontextv?V (H3)L(v)
vextendsinglevextendsingle
vextendsingle =
vextendsinglevextendsingle
vextendsingleuniontextv?V (H1)?V (H2)L(v)
vextendsinglevextendsingle
vextendsingle
=
vextendsinglevextendsingle
vextendsingle{uniontextv?V (H1)L(v)} uniontext { uniontextv?V (H2)L(v)}
vextendsinglevextendsingle
vextendsingle
=
vextendsinglevextendsingle
vextendsingleuniontextv?V (H1)L(v)
vextendsinglevextendsingle
vextendsingle +
vextendsinglevextendsingle
vextendsingleuniontextv?V (H2)L(v)
vextendsinglevextendsingle
vextendsingle -
vextendsinglevextendsingle
vextendsingle{uniontextv?V (H1)L(v)} intersectiontext {uniontextv?V (H2)L(v)}
vextendsinglevextendsingle
vextendsingle
(*) lessorequalslant |V(H1)| + |V(H2)| -
vextendsinglevextendsingle
vextendsingle{uniontextv?V (H1)?V (H2)L(v)}
vextendsinglevextendsingle
vextendsingle
(**)lessorequalslant |V(H1)|+|V(H2)|?
vextendsinglevextendsingle
vextendsingleV(H1)
intersectiondisplay
V(H2)
vextendsinglevextendsingle
vextendsingle=
vextendsinglevextendsingle
vextendsingleV(H1)
uniondisplay
V(H2)
vextendsinglevextendsingle
vextendsingle= |V(H3)|. (3.2)
[The inequality (*) is true since
vextendsinglevextendsingle
vextendsingleuniontextv?V (Hi)L(v))
vextendsinglevextendsingle
vextendsingle = |V(Hi)|, i = 1,2 by the assumption of
tightness and {uniontextv?V (H1)L(v)} intersectiontext {uniontextv?V (H2)L(v)} ? uniontextv?V (H1)?V (H2)L(v).
53
The inequality (**) is an application of HC to H0 = H1 ?H2 = < V(H1)?V(H2) >:
vextendsinglevextendsingle
vextendsingleuniontextv?V (H1)?V (H2)L(v)
vextendsinglevextendsingle
vextendsingle greaterorequalslant |V(H1)intersectiontextV(H2)|].
From inequalities (3.1) and (3.2), we see that the ends are equal and so it must be that
the middles were also equal. Hence the inequalities in (*) and (**) are actually equalities.
Thus H3 is L-tight and H0 as well, implied by equality at (**).
a50
By observing that S??V(H) ? S? is an independent set of vertices, I have the following
lemma.
Lemma 3.3 If [S? : ? ? C] is an HC+ (or HC++) satisfying family for G and L, then
for any induced subgraph H of G, [S??V(H) : ? ? C] is also an HC+ (respectively HC++)
satisfying family for G and L.
Lemma 3.4 Suppose K is a clique with a list assignment L, and K and L satisfy HC.
Suppose that for some color ?, removing ? from K wherever it appears results in a list
assignment which does not satisfy HC with K. Then some subclique K? of K is L-tight.
Further, ? ? L(K?).
Proof of theorem 3.3:
Suppose G and L satisfy HC+, and show that the new graph G has a proper L-
coloring. Let [S? : ? ? C] be an HC+ - satisfying family for G and L; H is HC+ and
hatwideK is a clique, i.e. hatwideK = Kn for some n greaterorequalslant 2. Let K = hatwideK ? v ? Kn?1. Since H is an
induced subgraph of G, HC+ on G and L means HC+ on H and L. Thus there is a
proper L-coloring of H.
54
Let P be the set of all colors that appear on the vertex of attachment, say the specific
vertex v, in the proper L-coloring of H.
H
?v
hatwideK
G:
Figure 3.2: Hall+ graph H, with an attached clique hatwideK
Define P as follows: P = {? ? C | for some proper L-coloring ? of H, ?(v) = ? }.
For ? ? P arbitrary, if I remove ? from all the lists on K, then I may as well assume
that the resulting list assignment to K does not satisfy Hall?s Condition. This is so because
if the new list did satisfy Hall?s Condition, then K being a clique means I can color. If one
puts a coloring of K without using ? together with a proper L-coloring of H using ? at v,
you get an L-coloring of G. We therefore see from lemma 3.4 that for each ? ? P, there is
an L - tight subclique say K? with ? on its lists.
By lemma 3.2 above applied | P |-1 times successively, I see that Kp = < uniontext??P K? >
is L-tight and since the ? value for each color ? is 1 (for cliques), we must have some vertex
of Kp in S? for each ? ? P (for all L-tight subgraphs). Thus ?? ? P, v negationslash? S?.
Now define a new list assignment Lprime on the graph H as follows:
Lprime(v) = L(v)\P, and Lprime(u) = L(u) for u negationslash= v.
55
Now H and Lprime can not satisfy HC+ because if they did, then by H ? Hall+, there
exists a proper Lprime-coloring of H. But such a proper Lprime-coloring will also be a proper L-
coloring for H given that L and Lprime coincide except at the vertex v and Lprime(v) ? L(v). But
I have eliminated P on Lprime i.e. the colors on L(v) that are in the proper L-colorings of H.
Hence there is no proper Lprime-coloring of H. Thus conclude that H and Lprime do not satisfy
HC+.
Now consider the definition of HC+ and note that it has two parts: the existence of
HC on one hand and an HC+ satisfying family as the other part. Thus the failure of
HC+ for H and Lprime means that at least one of the two parts in the definition must fail.
Case 1: If H and Lprime do not satisfy HC, then for some induced subgraph H1 of H, the
following must be true:
summationdisplay
??C
?(H1(?,Lprime)) < |V(H1)|. (3.3)
But L and Lprime are the same except at v. Also, H and L did satisfy HC and so the problem
must be at the vertex v itself. Thus, surely, H1 contains vertex v.
Let H2 = < H1 ? Kp > (see figure). This is a disjoint union because H1 ? H and
Kp ? K.
|V(H2)| = |V(H1)| + |V(Kp)| lessorequalslant
summationdisplay
??C
?(H2(?,L)) (3.4)
lessorequalslant
summationdisplay
??C
?(H1(?,Lprime)) +
summationdisplay
??C
?(Kp(?,L)) (3.5)
=
summationdisplay
??C
?(H1(?,Lprime)) + vextendsinglevextendsingle?u?Kp)L(u)vextendsinglevextendsingle (3.6)
=
summationdisplay
??C
?(H1(?,Lprime)) + |V(Kp)| (3.7)
56
< |V(H1)| + |V(Kp)| (3.8)
Thus |V(H1)| + |V(Kp)| < |V(H1)| + |V(Kp)| which is a contradiction.
Thus H and Lprime do satisfy HC but not HC+.
The inequality in (3.4) follows from the fact that G and L satisfy HC. The inequality
in (3.5) follows from the fact that the vertex independence number of a union is less than or
equal to that of its separate parts. Indeed, taking term by term sum, if a color ? negationslash? P, then
its independence number in H2 is less or equal to the sum of its independence number from
H1 and that from the clique Kp . However, if color ? ? P, then on its L-list, any maximum
independent set in H2(?,L), if it contains the vertex v, it will not contain any vertex of
Kp. Thus I can trade v for one vertex from Kp to obtain a maximum independent set in
H2(?,L) consisting of an independent set in H1(?,Lprime) and a vertex of Kp. On the other
hand, a maximum independent set in H2(?,L) not containing v is already of that form.
The details for (3.5) can be explained as follows: suppose U is a maximum independent
set in H2(?,L). Let U1 = U ?V(H1), and U2 = U ?V(Kp). Then U2 has a maximum of
one vertex. If ? negationslash? P, then from above, H2(?,L) = H2(?,Lprime) and since by definition
|U1|lessorequalslant ?(H1(?,Lprime)) and |U2|lessorequalslant ?(Kp(?,L)),
=? ?(H2(?,L)) = |U1| + |U2| lessorequalslant ?(H1(?,Lprime)) + ?(Kp(?,L)).
Now if ? ? P, then either v negationslash? U so that the inequality follows or v ? U in which case
U2 = ?; I can replace vertex v with some vertex of Kp to get a new maximum independent
set.
The equality in (3.6) holds because Kp is an L-tight clique.
The equality in (3.7) follows because Kp is L-tight. Finally the strict equality in (3.8)
follows from (3.3).
57
As a recap, we have proven that H and Lprime do satisfy HC but not HC+. Hence the
problem must come from the HC+ satisfying family. I had Kp = < uniontext??P K? > to be an
L-tight sub-clique of K = hatwideK?v ? Kn?1, for n greaterorequalslant 2, with every color in P appearing in Kp.
For every color ? appearing in Kp, |S?intersectiontextV(Kp)| = 1. So if ? ? P, then v negationslash? S?
because some u ? V(Kp)?S? and u is adjacent to v. Hence v negationslash? S?.
There must be some Lprime - tight subgraph, say hatwideH1 of H, such that for some color ? ? C,
vextendsinglevextendsingle
vextendsingleS? intersectiontextV(hatwideH1(?,Lprime))
vextendsinglevextendsingle
vextendsingle< ?(hatwideH1(?,Lprime)). Thus it must follow that v ? V(hatwideH1) because other than
on the vertex v, L and Lprime coincide.
Now define G1 = < hatwideH1uniontextKp >. Our aim at this stage is to show that G1 is L- tight.
This is done by letting G1 play H2 in the first part of our proof above.
Claim: G1 is L - tight.
Proof:
H
?va72a72
a72a72
a72a72
a72a72
hatwiderH1
hatwideK
G:
Figure 3.3: Hall+ graph H ? hatwideH1 and clique hatwideK
|V(hatwideH1)| + |V(Kp)| = |V(G1)| lessorequalslant
summationdisplay
??C
?(G1(?,L)) (3.9)
=
summationdisplay
??C\P
?(G1(?,L)) +
summationdisplay
??P
?(G1(?,L)) (3.10)
58
lessorequalslant
summationdisplay
??C\P
[?(hatwideH1(?,Lprime)) +?(Kp(?,L))] +
summationdisplay
??P
[?(hatwideH1(?,Lprime)) +?(Kp(?,L))] (3.11)
=
summationdisplay
??C
?(hatwideH1(?,Lprime)) +
summationdisplay
??C
?(Kp(?,L)) = |V(hatwideH1)| + |V(Kp)|, (3.12)
where the inequality in (3.9) follows from Hall?s Condition onG1 andL, and (3.10) follows by
breaking set C into two disjoint sets. Finally, for (3.11), one note first that the independence
number of a union of two graphs is at most the sum of the separate independence numbers.
Also, the replacement of L by Lprime in the first sum is a consequence of the fact that if ? negationslash? P,
then ?(hatwideH1(?,Lprime)) = ?(hatwideH1(?,L)). For the second sum, if ? ? P and you take a maximum
independent set in G1(?,L); if v belongs to that set, then we can delete v and replace it
with some vertex of Kp (i.e. trade places). The second equality in (3.12) is as a result of
hatwideH1 being Lprime - tight and Kp being L - tight.
Thus we see that the ends of the set of inequalities above are equal. Consequently, the
middle inequalities are forced to become equalities. Thus the inequality in (3.9) will become
an equality, giving |V(G1)| = summationtext??C ?(G1(?,L)) and so G1 is L - tight. The claim
is thus established.
As a further consequence,
|S?intersectiontextV(G1)| = ?(G1(?,L)) = ?(hatwideH1(?,Lprime)) + ?(Kp(?,L)), ?? ? C.
Recall that ? ? C is such that
vextendsinglevextendsingle
vextendsingleS? intersectiontextV(hatwideH1(?,Lprime))
vextendsinglevextendsingle
vextendsingle < ?(hatwideH1(?,Lprime)). We will see
that the assumption of the existence of ? leads to a contradiction, which will finish the
proof.
First suppose that ? negationslash? P =? hatwideH1(?,Lprime) = hatwideH1(?,L). We have
vextendsinglevextendsingle
vextendsingleS? intersectiontextV(hatwideH1(?,Lprime))
vextendsinglevextendsingle
vextendsingle + ?(Kp(?,L)) =
vextendsinglevextendsingle
vextendsingleS? intersectiontextV(hatwideH1(?,L))
vextendsinglevextendsingle
vextendsingle + |S? intersectiontextV(Kp(?,L))|
= |S? intersectiontextV(G1(?,L))| = ?(G1(?,L)) = ?(hatwideH1(?,Lprime)) + ?(Kp(?,L))
59
=?
vextendsinglevextendsingle
vextendsingleS? intersectiontextV(hatwideH1(?,Lprime))
vextendsinglevextendsingle
vextendsingle = ?(hatwideH1(?,Lprime)), contradicting the original statement that
vextendsinglevextendsingle
vextendsingleS? intersectiontextV(hatwideH1(?,Lprime))
vextendsinglevextendsingle
vextendsingle < ?(hatwideH1(?,Lprime)).
Now suppose that ? ? P =? v negationslash? S?.
=?
vextendsinglevextendsingle
vextendsingleS? intersectiontextV(hatwideH1(?,Lprime))
vextendsinglevextendsingle
vextendsingle =
vextendsinglevextendsingle
vextendsingleS? intersectiontextV(hatwideH1(?,L))
vextendsinglevextendsingle
vextendsingle, so the sequence of equalities just
above holds, and again I have a contradiction.
square
I will now state and prove a lemma that was stated in the introductory chapter.
Lemma 3.5 Hall?s Condition holds for G and L if and only if the inequality in Hall?s
Condition (equation (1.1)) holds for each connected induced subgraph of G.
Proof: If G and L satisfies Hall?s Condition, then the inequality holds for every subgraph
of G, and thus for every connected induced subgraph of G.
Now suppose the inequality in equation (1.1) holds for every induced subgraph of G.
If H is a subgraph of G, then H is a spanning subgraph of an induced subgraph hatwideH and for
each symbol ? ? C, H(?,L) is a spanning subgraph of hatwideH(?,L). Since H(?,L) is either equal
to hatwideH(?,L) or obtained from it by deleting edges, it follows that ?(H(?,L)) greaterorequalslant ?(hatwideH(?,L)).
Therefore, using the assumption that the inequality defining HC holds for hatwideH, I have
summationdisplay
??C
?(H(?,L)) greaterorequalslant
summationdisplay
??C
?(hatwideH(?,L)) greaterorequalslant |V(hatwideH)| = |V(H)|. (3.13)
Now suppose that the inequality defining HC holds for every connected induced subgraph
of G. To show that it holds for every subgraph of G, it suffices to show that it holds for
every induced subgraph of G from above. Suppose that H is an induced subgraph of G with
components H1,H2,...,Hk. Then H1,H2,...,Hk are induced subgraphs of G and for each
60
symbol ? ? C, H(?,L) is the disjoint union of H1(?,L),H2(?,L),...,Hk(?,L). Therefore,
by the assumption,
summationdisplay
??C
?(H(?,L)) =
summationdisplay
??C
ksummationdisplay
i=1
?(Hi(?,L)) =
ksummationdisplay
i=1
summationdisplay
??C
?(Hi(?,L)) (3.14)
greaterorequalslant
ksummationdisplay
i=1
|V(Hi)| = |V(H)|. (3.15)
Hence, I have inequality (1.1) and hence the lemma.
a50
Our next two results identifies two families of graphs that are always in the family of
Hall+ graphs.
First note that by a result of Changiz Eslahchi et al [4] and the definition of the hall
number given at the introduction, cycles with 4 or more vertices have hall number 2. This
means that if L is a list assignment to such a graph satisfying HC and |L(v)| greaterorequalslant 2 for
all vertices v, then there is a proper L-coloring of the cycle.
Proposition 3.3 All cycles with 4 or more vertices are Hall+
Proof:
??
?
wv
u
Cn = G:
Figure 3.4: Cycle with n vertices, Cn
61
Our aim is to show that if Cn, for n greaterorequalslant 4 and L satisfy HC+, then there exists a proper
L-coloring.
Suppose Cn, for n greaterorequalslant 4 and some list assignment L satisfy HC+ and let [S?;? ? C] be
an HC+ - satisfying family for Cn and L. Then since the hall number of Cn is 2, for n greaterorequalslant 4,
I may as well assume that some list is a singleton, say L(v) = {?}. Then v ? S?. Let u,w
be the vertices on either side of v on Cn. Consider Cn?uv i.e. Cn-minus the edge between
vertex u and v. Then P = Cn?uv is a path, and so every block is a clique. Thus P satisfies
Hall?s Condition with L. So P has a proper L-coloring in which the vertex v is colored ?.
One may as well suppose, without loss of generality that in every proper L-coloring of P,
the vertex u is always colored ?. Indeed, if there is some proper L-coloring of P in which
the vertex u is not colored with ?, then bring back the edge uv and get a proper L-coloring
of Cn and we will be done.
So if a new list assignment Lprime is defined by Lprime(u) = L(u)\{?} and L = Lprime otherwise,
then P and Lprime do not satisfy Hall?s Condition. So for some (connected) induced subgraph
H of P, I have summationtext??C ?(H(?,Lprime)) < |V(H)|.
Conclude that
(i) u ? V(H) and H is L-tight (since bringing back ? at u increases the independence
number ?(H?) by at most one).
Furthermore,(ii) u is in every maximum independent set H(?,L).
So u ? S? and this is a contradiction because by assumption, L(v) = {?} thus forcing
v ? S?. But then u ? S? and v ? S? is a contradiction as uv ? E(Cn). This forces us to
conclude that Cn ? Hall+. a50
Proposition 3.4 K4 - minus - an edge is Hall+.
62
Proof:
a0
a0
a0
a0
a0
a0
a0
a0
a0
a0
a0
a0
a0a0a64a64
a64
a64
a64
a64
a64
a64
a64
a64
a64
a64
a64a64c
a
d
b
circledot
circledot
circledot
circledot
G:
Figure 3.5: K4 - minus - an edge
Let L be a list assignment to G = K4 - minus - an edge, such that G and L satisfy
HC+. Then in particular, G and L satisfy HC. Since the hall number of G is 2, if I had
|L(v)| greaterorequalslant 2, ?v ? V(G), then there must be a proper L-coloring of G. Let us suppose
that L(v) = {?} for some vertex v ? V(G) and let the collection [S? : ? ? C] be an HC+
- satisfying family for G and L. From here the proof is almost word for word like that of
Proposition 3.3; v has a neighbor u (in fact, there are two choices for u) such that G?uv
is Hall. Let Lprime be defined as in the proof preceding, and everything goes through.
a50
The next example shows that attaching two Hall+ graphs at one vertex does not
necessarily result to a Hall+ graph.
Example 3.2
Notice that G satisfies HC+ but cannot be properly colored.
Obviously, a graph Gprime obtained by contracting an edge e of a clique G is still a clique.
Since Hall graphs are graphs with blocks being cliques, we see that contracting an edge of
a Hall graph results in a Hall graph.
63
a0
a0
a0
a0
a0
a0a0a64a64
a64
a64
a64
a64a64
a64
a64
a64a64
a0
a0
a0a0 a64a64
a64a64
a0
a0
a0a0
{b,c}
{a,c}
{b,d}
{a,d}
{a,b} {c,d} {a,b}v
circledot
circledot
circledot
circledot
circledotcircledot circledotG:
Figure 3.6: Attached Hall+ graphs at vertex v that does not yield a Hall+ graph
Question: Does the contraction of an edge of a Hall+ or Hall++ graph leave it in
the same category, as was the case of Hall graphs?
64
Chapter 4
HALL* AND HALL** GRAPHS
4.1 Introduction
The main result in this chapter will be one similar to theorem 3.3 of the previous
chapter. Here, I shall similarly prove that if a graph H ? Hall* and a clique hatwideK is attached
to a vertex v ? V(H), then the resulting graph G will also be Hall*. A deduction from
this will be a similar conclusion for Hall** graphs. For completeness, I will recall some
definitions stated earlier.
Definition 4.1 G is a Hall* graph if whenever G, L satisfy HC*, there is a proper L-
coloring of G.
Definition 4.2 G is a Hall** graph if whenever G, L satisfy HC**, there is a proper
L-coloring of G.
Example 4.1
Consider H to be the six 3 by 2 sub squares induced by the coordinates:
< (1,1),(1,2),(2,1),(2,2),(3,1),(3,2) > of the Aharoni-Hilton example, figure(2.2).
H has 19 L-tight induced subgraphs.
Indeed, let the list assignment on H be as in chapter 2. H and its list assignments are
shown in figure(4.1).
65
{1} {1,2}
7 {2,3}
{1,5} 6
Figure 4.1: 3? 2 Rectangle of cells
The 19 L-tight induced subgraphs of H are as follows:
< (1,1) >, < (2,1) >, < (3,2) >, < (1,1),(1,2) >, < (1,1),(2,1) >, < (1,1),(3,2) >,
< (1,1),(3,1) >, < (2,1),(3,2) >, < (1,1),(1,2),(2,1) >, < (1,1),(2,1),(3,1) >,
< (1,1),(1,2),(2,2) >, < (1,1),(1,2),(3,2) >, < (1,1),(2,1),(3,2) >, < (1,1),(3,1),(3,2) >,
< (1,1),(1,2),(2,1),(2,2) >, < (1,1),(1,2),(2,1),(3,2) >, < (1,1),(2,1),(3,1),(3,2) >,
< (1,1),(1,2),(2,2),(3,2) >, < (1,1),(1,2),(2,1),(2,2),(3,2) >.
For instance, when T = < (1,1),(1,2),(2,1),(2,2),(3,2) >, then ?(T4) = 0 = ?(T5), while
?(T?) = 1 for ? ? {1,2,3,6,7}. Thus
7summationdisplay
?=1
?(T?) = 1 + 1 + 1 + 0 + 0 + 1 + 1 = 5 = | V(T) | .
This shows that T is L-tight.
H is properly L-colorable because I can actually fill each cell using say,
?((1,1)) = 1, ?((1,2)) = 2, ?((2,1)) = 7, ?((2,2)) = 3, ?((3,1)) = 5, ?((3,2)) = 6.
The fact that H is properly L-colorable implies that H and L satisfy HC**.
However, H is not HALL**, (and therefore not HALL*), as shown by the following
list assignment:
66
{1,3} {2,3}
{1,2} {1,2}
{2,3} {1,3}
Figure 4.2: 3? 2 Rectangle of cells with no completion
This example demonstrates how tedious it can be to verify HC* or HC**. (In our
example, six cells have as many as 19 tight subgraphs. For the complete 7?7 in figure(2.2),
the number of tight subgraphs to be considered can be very large, and to verify HC* by
brute force, eachL-tight subgraph must be considered together with every induced subgraph
containing it.) Thus HC* and HC** are of theoretical interest alone, so far.
4.2 Closure Property
I now state and prove the main result in this chapter.
Theorem 4.1 If a graph H ? Hall*, and a graph G is obtained from H by attaching a
clique to an arbitrary vertex v of H, then G ? HALL*. Thus the class of HALL* graphs
is closed under attachment of cliques. The same is true if Hall* is replaced by Hall**.
Notice that the statement is very similar to that of theorem(3.3) of the previous chapter.
I will build the proof with this in mind.
Proof:
Let K = hatwideK ?v ? Kn?1, for n greaterorequalslant 2 and suppose L is a list assignment on G such that
G and L satisfy HC*. I must show that there is a proper L-coloring of G.
Assume the contrary. By lemma 3.1, every induced subgraph H of G with L restricted
on V(H) will satisfy HC*. Now suppose there is no proper L-coloring of G.
67
H
?v
hatwideK
G:
Figure 4.3: Hall* graph H, with an attached clique hatwideK
Since H ? G and G and L satisfy HC*, it must be that H and L restricted on V(H)
will satisfy HC*. Since H ? Hall*, it follows that there is a proper L coloring of H.
However, because there is no proper L-coloring of G for every proper L-coloring of H, if the
color on the vertex v is removed from the lists on V(K), then K and the new list assignment
do not satisfy HC.
Define the set of symbols P = {? ? C | for some proper L-coloring ? of H, ?(v) = ? }
We therefore see from lemma 3.4 that for every symbol ? ? P, there is an L-tight
subclique of the clique K with ? appearing on its lists. Hence there is a tight complete
subgraph Kp of K with all colors of P on its lists. Now define a new list assignment Lprime on
the graph H as follows:
Lprime(v) = L(v)\L(Kp), and Lprime(u) = L(u) for all u ? V(H ?v).
Then it must be that H and Lprime do not satisfy HC* because there is no proper Lprime-
coloring of H, but they do satisfy Hall?s condition by the argument for the analogous claim
in the proof of theorem (3.3) in chapter 3. I can therefore conclude this far that H and Lprime
so defined do satisfy HC but do not satisfy HC*.
68
HC* failing means there is some induced subgraph Hprime of H and someLprime-tight subgraph
Tprime of Hprime such that the inequality in HC* fails. Thus I have
summationdisplay
??C
?(Hprime(?,Lprime) | Tprime(?,Lprime)) < vextendsinglevextendsingleV(Hprime)vextendsinglevextendsingle. (4.1)
Thus the vertex v must belong to Hprime since Lprime = L on the graph H?v and H and L satisfy
HC*.
With v ? V(Hprime) and Tprime ? Hprime, two cases arise: v ? V(Tprime) and v negationslash? V(Tprime).
H
?va72a72
a72a72
a72a72
a72a72
Hprime
Tprime
hatwideK
G:
Figure 4.4: Hall* graph H ? Hprime ? Tprime, and clique hatwideK
Let Hprimeprime = < Hprime ?Kp > be the subgraph induced by the disjoint union of Hprime and Kp
and let Tprimeprime = < Tprime ? Kp > be the subgraph induced by the disjoint union of Tprime and Kp.
Recalling that Tprime is an Lprime-tight subgraph of Hprime, an induced subgraph of H containing the
vertex v, I have the following two claims:
Claim 1: Tprimeprime = < Tprime ?Kp > is L-tight;
Claim 2: summationtext??C ?(Hprimeprime(?,L) | Tprimeprime(?,L)) < |V(Hprimeprime)|.
69
Note that if claim 2 holds, then it will contradict the hypothesis that G and L satisfy
HC*; hence I can conclude that theorem 4.1 is true.
Remark 4.1
Before getting into the proof, it is worth remarking that it is a fairly known result that
if each component of a graph G and a list assignment L satisfy HC, then G and L will
satisfy HC. Moreover, if each component is L-tight, then so too is the whole graph.
Proof of Claim 1:
If v negationslash? V(Tprime), then Lprime = L on Tprimeprime and so Tprimeprime must also be L-tight as the disjoint union
of two L-tight subgraphs. Now suppose v ? V(Tprime). If the symbol ? negationslash? L(Kp) , then
?(Tprimeprime(?,L)) lessorequalslant ?(Tprime(?,L)) + ?(Kp(?,L)) = ?(Tprime(?,Lprime)) + ?(Kp(?,L)).
On the other hand, if ? ? L(Kp), then I will prove the following claim:
?(Tprimeprime(?,L)) lessorequalslant ?(Tprime(?,Lprime)) + ?(Kp(?,L)).
Noting that Kp is a clique in which case ?(Kp(?,L)) = 1, one can equivalently prove
that
?(Tprimeprime(?,L)) lessorequalslant ?(Tprime(?,Lprime)) + 1. (4.2)
Indeed, let W be a maximum independent set of vertices in Tprimeprime(?,L), then
Case (i): if v ? W, we see that W contains no vertices of the clique Kp and so W \{v}
is an independent set in Tprimeprime(?,Lprime) so |W \{v}| = |W| ? 1 lessorequalslant ?(Tprime(?,Lprime)
?? |W| lessorequalslant ?(Tprime(?,Lprime) + 1
and by the definition of W being a maximum independent set in Tprimeprime(?,L), it follows that
?(Tprimeprime(?,L)) lessorequalslant ?(Tprime(?,Lprime)) + 1, which is equation (4.2).
70
Case (ii): if v negationslash? W, then W consists of exactly one vertex of Kp together with an
independent set in Tprime(?,Lprime). This immediately gives |W| lessorequalslant ?(Tprime(?,Lprime) + 1,
hence equation (4.2).
Finally, by Hall?s Condition and the definition of Tprimeprime,
vextendsinglevextendsingleV(Tprimeprime)vextendsinglevextendsingle lessorequalslant summationdisplay
??C
?(Tprimeprime(?,L)) lessorequalslant
summationdisplay
??C
?(Tprime(?,Lprime)) +
summationdisplay
??C
?(Kp(?,L)) (4.3)
= vextendsinglevextendsingleV(Tprime)vextendsinglevextendsingle + |V(Kp)| = vextendsinglevextendsingleV(Tprimeprime)vextendsinglevextendsingle (4.4)
where the first equality in (4.4) follows because Tprime is Lprime-tight and Kp is L-tight and the last
equality follows from the fact that Tprimeprime = < Tprime ?Kp >. Thus Tprimeprime is L-tight.
Proof of Claim 2:
I will aim at showing that
summationdisplay
??C
?(Hprimeprime(?,L) | Tprimeprime(?,L)) < vextendsinglevextendsingleV(Hprimeprime)vextendsinglevextendsingle, (4.5)
which will contradict the assumption that G and L satisfy HC*.
summationdisplay
??C
?(Hprimeprime(?,L) | Tprimeprime(?,L)) =
summationdisplay
??C\L(Kp)
?(Hprimeprime(?,L) | Tprimeprime(?,L))+
summationdisplay
??L(Kp)
?(Hprimeprime(?,L) | Tprimeprime(?,L))
(4.6)
=
summationdisplay
??C\L(Kp)
?(Hprime(?,Lprime) | Tprime(?,Lprime)) +
summationdisplay
??L(Kp)
?(Hprimeprime(?,L) | Tprimeprime(?,L)) (4.7)
lessorequalslant
summationdisplay
??C\L(Kp)
?(Hprime(?,Lprime) | Tprime(?,Lprime)) +
summationdisplay
??L(Kp)
?(Hprime(?,Lprime) | Tprime(?,Lprime))+|L(Kp)| (4.8)
where the equality in (4.7) follows because if the symbol ? is not in L(Kp), then
Hprimeprime(?,L) = Hprime(?,Lprime) and Tprimeprime(?,L) = Tprime(?,Lprime).
71
The inequality in (4.8) is a consequence of the following claim:
Claim:
If ? ? L(Kp), then
?(Hprimeprime(?,L) | Tprimeprime(?,L)) lessorequalslant ?(Hprime(?,Lprime) | Tprime(?,Lprime)) + 1. (4.9)
Proof of Claim:
Suppose U is a maximum independent set of vertices in Tprimeprime(?,L) and W is an inde-
pendent set of vertices in Hprimeprime(?,L) containing the set U and suppose |W| = ?(Hprimeprime(?,L) |
Tprimeprime(?,L)). If U contains a vertex x of Kp, then W does not contain the vertex v nor any
other vertex of Kp; same for U. So Uprime = U \{x} is an independent set of vertices in
Tprime(?,Lprime), contained in W \ {x}, an independent set of vertices in Hprime(?,Lprime). I claim
that Uprime is a maximum independent set of vertices in Tprime(?,Lprime). For, if tildewideU is any independent
set of vertices in Tprime(?,Lprime) then, since ? negationslash? Lprime(v), whence v negationslash? tildewideU, it follows that tildewideU ?{x} is
an independent set of vertices in Tprimeprime(?,L), whence
vextendsinglevextendsingle
vextendsingletildewideU ?{x}
vextendsinglevextendsingle
vextendsingle =
vextendsinglevextendsingle
vextendsingletildewideU
vextendsinglevextendsingle
vextendsingle + 1 lessorequalslant |U| = |Uprime ?{x}| = |Uprime| + 1.
From the fact that Uprime = U \{x} is an independent set of vertices of Tprime(?,Lprime)
contained in W \{x}, an independent set of vertices in Hprime(?,Lprime), it follows that
|W \{x}| = |W|?1 = ?(Hprimeprime(?,L) | Tprimeprime(?,L))?1 lessorequalslant ?(Hprime(?,Lprime) | Tprime(?,Lprime))
?? |W| lessorequalslant ?(Hprime(?,Lprime) | Tprime(?,Lprime)) + 1.
Now if U does not contain a vertex of Kp, then since ? ? L(Kp), it must be that
v ? U because if v negationslash? U then adding a vertex of Kp to U would give a larger independent
set of vertices of Tprimeprime(?,L). Therefore v ? V(Tprime(?,L)) and since W is an independent set
containing U, it must be that W contains no vertices of Kp. Thus U\{v} is a maximum
72
independent set of vertices in Tprime(?,Lprime) because if not, take say tildewideU an independent set of
vertices in Tprime(?,Lprime) such that |U| > |U\{v}|. Then for any y ? Kp(?,L), tildewideU ?{y} is an
independent set of vertices in Tprimeprime(?,L) bigger than U, contrary to the assumption that U
is a maximum independent set of vertices in Tprimeprime(?,L).
Recalling that W \{v} contains U \{v} one can complete the prove of the claim as
follows:
|W \{v}| = |W|?1 lessorequalslant ?(Hprime(?,Lprime) | Tprime(?,Lprime))
?? |W| lessorequalslant ?(Hprime(?,Lprime) | Tprime(?,Lprime)) + 1 which is (4.9).
To complete the proof, note that the left hand side of (4.6) and the right hand side of
inequality (4.8) gives
summationdisplay
??C
?(Hprimeprime(?,L) | Tprimeprime(?,L)) lessorequalslant
summationdisplay
??C
?(Hprime(?,Lprime) | Tprime(?,Lprime)) + |L(Kp)| (4.10)
< vextendsinglevextendsingleV(Hprime)vextendsinglevextendsingle + |V(Kp)| = vextendsinglevextendsingleV(Hprimeprime)vextendsinglevextendsingle. (4.11)
from (4.1) above coupled with the definition of Hprimeprime and Kp being a tight clique.
To get a corresponding proof for the Hall** case, we assume the notation of the
preceding proof and proceed as follows:
suppose L is a list assignment on G such that G and L satisfy HC**. One must show
that there is a proper L-coloring of G.
Assume the contrary. By lemma 3.1, every induced subgraph H of G with L restricted
on V(H) will satisfy HC**. Thus H and L satisfy HC** as G, L does.
73
Since H ? Hall**, it follows that there is a proper L coloring of H. Now suppose
there is no proper L-coloring of G. Then for every proper L-coloring of H, if the color on v
is removed from the lists on V(K), then K and the new list assignment do not satisfy HC.
As before, define P = {? ? C | for some proper L-coloring ? of H, ?(v) = ? }.
We therefore see from lemma 3.4 that for every symbol ? ? P, there is an L-tight
subclique of the clique K with ? appearing on its lists. Hence there is a tight complete
subgraph Kp of K with all colors of P on its lists.
Now define a new list assignment Lprime on the graph H as follows:
Lprime(v) = L(v)\L(Kp), and Lprime(u) = L(u) for all u ? V(H ?v). Then as in the claim in the
proof of theorem (3.3) I can conclude that H and Lprime satisfy HC but do not satisfy HC**.
Hence there must be an induced subgraph Hprime of H and some Lprime-tight subgraph Tprime of
Hprime such that the inequality in HC** fails, i.e. such that
summationdisplay
??C
min
TprimetriangleleftHprime
?(Hprime(?,Lprime)|Tprime(?,Lprime)) greaterorequalslant |V(Hprime)|, (4.12)
where the minimum is taken over each Lprime-tight subgraph Tprime of Hprime.
Thus v ? V(Hprime) since Lprime = L on the graph H ?v and H and L satisfy HC**.
With v ? V(Hprime) and Tprime ? Hprime, either v ? V(Tprime) and v negationslash? V(Tprime).
As in the preceding proof, let Hprimeprime = < Hprime?Kp >; and for each Tprime an Lprime-tight subgraph
of Hprime, let Tprimeprime = < Tprime ?Kp >. Then by an argument similar to that in the preceding proof,
it must be that Tprimeprime is L-tight in Hprimeprime.
Claim:
summationdisplay
??C
min
eTtriangleleftHprimeprime
?(Hprimeprime(?,L)|tildewideT(?,L)) < |V(Hprimeprime)| = |V(Hprime)|+|V(Kp)|, (4.13)
74
where the minimum is taken over each L-tight subgraph tildewideT of Hprimeprime.
This claim will contradict the hypothesis that G and L satisfy HC**; hence we can
conclude.
Indeed, by the preceding proof for equation 4.9, one conclude that for each ? ? L(Kp),
and each Lprime-tight subgraph Tprime of Hprime,
?(Hprimeprime(?,L) | Tprimeprime(?,L)) lessorequalslant ?(Hprime(?,Lprime) | Tprime(?,Lprime)) + 1. (4.14)
Taking minimum respectively over tildewideT an L-tight subgraph of Hprimeprime or over Tprime an Lprime-tight
subgraph of Hprime for each symbol ?, and noting that Tprimeprime =< Tprime ?Kp > one obtain
summationdisplay
??C
min
eTtriangleleftHprimeprime
?(Hprimeprime(?,L)|tildewideT(?,L)) lessorequalslant
summationdisplay
??C
min
TprimetriangleleftHprime
?(Hprimeprime(?,L)|Tprimeprime(?,L)) (4.15)
=
summationdisplay
??C\L(Kp)
min
TprimetriangleleftHprime
?(Hprimeprime(?,L)|Tprimeprime(?,L)) +
summationdisplay
??L(Kp)
min
TprimetriangleleftHprime
?(Hprimeprime(?,L)|Tprimeprime(?,L)) (4.16)
=
summationdisplay
??C\L(Kp)
min
TprimetriangleleftHprime
?(Hprime(?,Lprime)|Tprime(?,Lprime)) +
summationdisplay
??L(Kp)
min
TprimetriangleleftHprime
?(Hprimeprime(?,L)|Tprimeprime(?,L)) (4.17)
lessorequalslant
summationdisplay
??C\L(Kp)
min
TprimetriangleleftHprime
?(Hprimeprime(?,L)|Tprimeprime(?,L)) +
summationdisplay
??L(Kp)
min
TprimetriangleleftHprime
?(Hprime(?,Lprime)|Tprime(?,Lprime)) +|L(Kp)|
(4.18)
lessorequalslant
summationdisplay
??C
min
TprimetriangleleftHprime
?(Hprime(?,Lprime)|Tprime(?,Lprime)) + |L(Kp)| (4.19)
< vextendsinglevextendsingleV(Hprime)vextendsinglevextendsingle + |V(Kp)| = vextendsinglevextendsingleV(Hprimeprime)vextendsinglevextendsingle. (4.20)
Where the inequality in (4.18) follows from (4.14) while inequalities (4.19) and (4.20) follows
from (4.1) given earlier coupled with the definition of Hprimeprime and Kp being a tight clique.
square
75
Remark 4.2
One could rephrase the proof architecture by supposing that G, L satisfy HC and H,
L satisfy HC* (or respectively HC**) but there is no proper L-coloring of G. One then
show that G, L do not satisfy HC* (or respectively HC**).
76
Bibliography
[1] L. D. Andersen and A. J. W. Hilton, Thank Evans!. Proc. London Math. Soc. 47 (3)
(1983), 507-522.
[2] B. B. Bobga and P. D. Johnson Jr., Completing Partial Latin Squares: Cropper?s
Problem, Congressus Numerantium, 188 (2007), 211-216.
[3] H. L. Buchanan and M. N. Ferencak, On completing Latin squares, J. Comb. Math.
and Comb. Comp., 34 (2000), 129-132.
[4] Changiz Eslachi and M. Johnson, Characterization of graphs with Hall number 2, J.
Graph theory 45 (2004), no. 2 81-100.
[5] C. Colbourn, The complexity of completing partial latin squares, Discrete Appl. Math.,
8 (1984), 151158.
[6] M. M. Cropper, J. L. Goldwasser, A. J. W. Hilton, D. G. Hoffman, P. D. Johnson
Jr. Extending the disjoint-representatives theorems of Hall, Halmos, and Vaughan to
list-multicolorings of graphs, Journal of Graph Theory, 33 no.4 (2000), 199-219.
[7] D. Donovan, The completion of partial latin squares, Australasian Journal of Combi-
natorics, 22 (2000), 247-264.
[8] Douglas B. West, Introduction to Graph Theory, 2nd Ed., Pearson Edu., 2005.
[9] Erd?os, Rubin and Taylor, Choosability in Graphs. Proceedings of the West Coast Con-
ference on Combinatorics, Graph Theory and Computing, Congressus Numerantium,
26 (1979), 125-157.
[10] T. Evans, Embedding incomplete latin rectangles, Amer. Math. Monthly, 67 (1960),
958-961.
[11] M. Hall, An Existence Theorem for latin squares, Bull. Amer. Math. Soc. 51 (1945),
387-388.
[12] P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935), 26-30.
[13] A. J. W. Hilton and P. D. Johnson Jr., A variation of Ryser?s theorem and a necessary
condition for the list-colouring problem, Chap. 10, pp. 135-143, Graph Colourings, Ray
Nelson and Robin Wilson, Editors; Pitman Research Notes in Mathematics Series 218,
Longman Scientific and Technical with John Wiley and Sons, Harlow, Essex, and New
York, 1990.
77
[14] A. J. W. Hilton and P. D. Johnson Jr., Extending Hall?s theorem, Topics in Com-
binatorics and Graph Theory: Essays in Honour of Gerhard Ringel, Physica-Verlag,
Heidelberg, 1990, 359-371.
[15] A. J. W. Hilton and P. D. Johnson Jr., and E. B. Wantland, The Hall number of a
simple graph, Congressus Numerantium, 121 (1996), 161-182.
[16] A. J. W. Hilton and P. D. Johnson Jr., List multicolorings of graphs with measurable
sets, Journal of Graph Theory, 54 no. 3 (2007) 179-193.
[17] D. G. Hoffman, Completing commutative latin squares with prescribed diagonals, Eu-
ropean J. Combinatorics, 4 (1983), 33-35.
[18] C. A. Rodger, Embedding an incomplete latin square in a latin square with a prescribed
diagonal, Discrete Math., 51 (1984), 73-89.
[19] H. J. Ryser, A combinatorial theorem with an application to Latin squares, Proc.
Amer. Math. Soc., 2 (1951), 550-552.
[20] V. G. Vizing, Coloring the Vertices of a Graph in Prescribed Colors. (Russian)
Diskret. Analiz. No. 29 Metody Diskret. Anal. V. Teorii Kodov i Shem,29 (1976), 3-10,
101(MR5816371).
78