Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Available in electronic format
Available in print format
Bulletin of the American Mathematical Society
Bulletin of the American Mathematical Society
ISSN 1088-9485(e) ISSN 0273-0979(p)

     

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 $ {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:

[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:

DOI: 10.1090/S0273-0979-1993-00430-0
PII: S 0273-0979(1993)00430-0
Copyright of article: Copyright 1993, American Mathematical Society




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia