Given any assignment of 
-element
sets to the 
locations of a square 
array, is it always possible to find a partial
Latin square? The fact that such a partial
Latin square can always be found for a 
array can be proven analytically, and techniques were
developed which also proved the existence for 
and 
arrays. However, the general problem eluded solution
until it was answered in the affirmative by Galvin in 1993 using results of Janssen
(1993ab) and F. Maffray.
Dinitz Problem
See also
Partial Latin SquareExplore with Wolfram|Alpha
References
Chetwynd, A. and Häggkvist, R. "A Note on List-Colorings." J. Graph Th. 13, 87-95, 1989.Cipra, B. "Quite Easily Done." In What's Happening in the Mathematical Sciences 2, pp. 41-46, 1994.Erdős, P.; Rubin, A.; and Taylor, H. "Choosability in Graphs." Congr. Numer. 26, 125-157, 1979.Häggkvist, R. "Towards a Solution of the Dinitz Problem?" Disc. Math. 75, 247-251, 1989.Janssen, J. C. M. "The Dinitz Problem Solved for Rectangles." Bull. Amer. Math. Soc. 29, 243-249, 1993a.Janssen, J. C. M. Even and Odd Latin Squares. Ph.D. thesis. Lehigh University, 1993b.Kahn, J. "Recent Results on Some Not-So-Recent Hypergraph Matching and Covering Problems." Proceedings of the Conference on Extremal Problems for Finite Sets. Visegràd, Hungary, 1991.Kahn, J. "Coloring Nearly-Disjoint Hypergraphs with
Colors." J. Combin. Th.
Ser. A 59, 31-39, 1992.Referenced on Wolfram|Alpha
Dinitz ProblemCite this as:
Weisstein, Eric W. "Dinitz Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DinitzProblem.html