- AUETD Home
- View Item

## Some Necessary Conditions for List Colorability of Graphs and a Conjecture on Completing Partial Latin Squares

##### Date

2008-12-15##### Author

Bobga, Benkam

##### Type of Degree

Dissertation##### Department

Mathematics and Statistics##### Metadata

Show full item record##### Abstract

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 completion
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.