Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



The Dinitz problem solved for rectangles

Author: Jeannette C. M. Janssen
Journal: Bull. Amer. Math. Soc. 29 (1993), 243-249
MSC (2000): Primary 05B15; Secondary 05C15
MathSciNet review: 1215310
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The Dinitz conjecture states that, for each n and for every collection of n-element sets $ {S_{ij}}$, an $ n \times n$ partial latin square can be found with the $ (i,j){\text{th}}$ entry taken from $ {S_{ij}}$. The analogous statement for $ (n - 1) \times n$ rectangles is proven here. The proof uses a recent result by Alon and Tarsi and is given in terms of even and odd orientations of graphs.

References [Enhancements On Off] (What's this?)

  • [AT] N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), 125-134. MR 1179249 (93h:05067)
  • [BHa] B. Bollobàs and A. J. Harris, List colourings of graphs, Graphs and Combinatorics 1 (1985), 115-127. MR 951773 (89e:05086)
  • [BHi] B. Bollobàs and H. R. Hind, A new upper bound for the list chromatic number, Discrete Math. 74 (1989), 65-75. MR 989123 (90g:05078)
  • [CH] Amanda Chetwynd and Roland Häggkvist, A note on list-colorings, J. Graph Theory 13 (1989), 87-95. MR 982870 (90a:05081)
  • [ERT] P. Erdös, A. Rubin, and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979), 125-157. MR 593902 (82f:05038)
  • [J] Jeannette C. M. Janssen, Even and odd latin squares, Lehigh Univ. doctoral dissertation, 1993.
  • [H] Roland Häggkvist, Towards a solution of the Dinitz problem?, Discrete Math. 75 (1989), 247-251. MR 1001399 (90f:05022)
  • [K1] Jeff Kahn, 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.
  • [K2] Jeff Kahn, Coloring nearly-disjoint hypergraphs with $ n + o(n)$ colors, J. Combin. Theory Ser. A 59 (1992), 31-39. MR 1141320 (93b:05127)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 05B15, 05C15

Retrieve articles in all journals with MSC (2000): 05B15, 05C15

Additional Information

Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society