scientific article; zbMATH DE number 15164

[For the entire collection see Zbl 0679.00004.] Surprisingly little has to been done to settle the following, ten years old conjecture of Jeff Dinitz: Conjecture 1: Suppose \(A\) is an \(m \times m\) array of \(m\)-sets. Then it is always possible to choose one element from each set in such way that no element is chosen twice in the same row or in the same column of \(A\). Except for an easy vertification of the truth of this conjecture for \(m \leq 3\) nothing has happened until 1986. That year \textit{R. Häggkvist} [Discrete Math. 75, No. 1-3, 247-251 (1989; Zbl 0669.05014)] proved the following Theorem 1: Let \(L\) be an \(m \times r\) array of \(m\)-sets with \(r \leq 2m/7\). Then it is possible to choose one element from each set keeping the chosen elements distinct in every row and in every column of \(L\). With the methods used in [Discrete Math. 75, No. 1-3, 247-251 (1989; Zbl 0669.05014)] it is possible to increase slightly the constant 2/7, but there still remains a large gap between this result and the original conjecture of Dinitz. On the other hand this problem has been a source of some new exciting ideas in the theory of graph colouring. The concept of choosability is a natural generalization of Dinitz's problem and was first formulated by \textit{R. Erdős, A. L. Rubin and H. Taylor} [Choosability in graphs. Combinatorics, graph theory and computing, Proc. West Coast Conf. Arcata/Calif. 1979, 125-157 (1980; Zbl 0469.05032)].

Recommendations

Cited in

(9)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3977503)