Completing Partial Latin Squares: Cropper's Problem

摘要

The problem of completing a partial n x 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-iu cells. Hall's condition is a fairly well known 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 complction of a partial latin square. We show that the answer is "yes" when the fillcd-in cells form 1. a sub-rectangle, or 2. a sub-rectangle minus one cell. In the former case, Hall's condition implies Ryser's condition.