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

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.