The Dinitz problem solved for rectangles
HTML articles powered by AMS MathViewer
- by Jeannette C. M. Janssen PDF
- Bull. Amer. Math. Soc. 29 (1993), 243-249 Request permission
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
- N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), no. 2, 125–134. MR 1179249, DOI 10.1007/BF01204715
- B. Bollobás and A. J. Harris, List-colourings of graphs, Graphs Combin. 1 (1985), no. 2, 115–127. MR 951773, DOI 10.1007/BF02582936
- B. Bollobás and H. R. Hind, A new upper bound for the list chromatic number, Discrete Math. 74 (1989), no. 1-2, 65–75. Graph colouring and variations. MR 989123, DOI 10.1016/0012-365X(89)90199-4
- Amanda Chetwynd and Roland Häggkvist, A note on list-colorings, J. Graph Theory 13 (1989), no. 1, 87–95. MR 982870, DOI 10.1002/jgt.3190130112
- Paul Erdős, Arthur L. Rubin, and Herbert Taylor, Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979) Congress. Numer., XXVI, Utilitas Math., Winnipeg, Man., 1980, pp. 125–157. MR 593902 Jeannette C. M. Janssen, Even and odd latin squares, Lehigh Univ. doctoral dissertation, 1993.
- Roland Häggkvist, Towards a solution of the Dinitz problem?, Discrete Math. 75 (1989), no. 1-3, 247–251. Graph theory and combinatorics (Cambridge, 1988). MR 1001399, DOI 10.1016/0012-365X(89)90091-5 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.
- Jeff Kahn, Coloring nearly-disjoint hypergraphs with $n+o(n)$ colors, J. Combin. Theory Ser. A 59 (1992), no. 1, 31–39. MR 1141320, DOI 10.1016/0097-3165(92)90096-D
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Bull. Amer. Math. Soc. 29 (1993), 243-249
- MSC (2000): Primary 05B15; Secondary 05C15
- DOI: https://doi.org/10.1090/S0273-0979-1993-00430-0
- MathSciNet review: 1215310