Completing partial latin squares: Cropper's problem
by
Peter Johnson
Auburn University
Coauthors: Benkam Bobga, Anthony Hilton

Hall's Condition on a graph and an assignment of lists to its vertices is a necessary condition for a proper coloring of the graph from the lists; the condition descends from Phillip Hall's theorem on systems of distinct representatives, which can be construed as saying that when the graph involved is a clique, Hall's Condition suffices for a proper list coloring. In general it seems that circumstances in which Hall's Condition suffices for a proper list coloring are rare. The problem of completing a partial latin square is is a list coloring problem in which both the graph and the list assignment are very special. Cropper's problem is the question: Does Hall's Condition suffice for a proper coloring in this special class of list-coloring problems? We review the evidence and prove several theorems of the form: If the prescribed cells form such-and-such a configuration, and Hall's Condition is satisfied, then the partial latin square is completable.

Date received: April 9, 2008