|
The Dinitz problem solved for rectangles
Author(s):
Jeannette C. M.
Janssen
Journal:
Bull. Amer. Math. Soc.
29
(1993),
243-249.
MSC (2000):
Primary 05B15;
Secondary 05C15
MathSciNet review:
1215310
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
Abstract:
The Dinitz conjecture states that, for each n and for every collection of n-element sets , an partial latin square can be found with the entry taken from . The analogous statement for 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:
-
- [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
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:
DOI:
10.1090/S0273-0979-1993-00430-0
PII:
S 0273-0979(1993)00430-0
Copyright of article:
Copyright
1993,
American Mathematical Society
|