4
$\begingroup$

I would like to ask if someone knows about good books or online articles about The Dinitz problem or maybe someone can explain the problem a little.

Consider $n^2$ cells arranged in an $( n \times n)$-square, and let $(i,j)$ denote the cell in row $i$ and columns $j$. Suppose that for every cell $(i,j)$ we are given a set $C(i,j)$ of $n$ colors.
Is it then always possible to color the whole array by picking for each cell $(i,j)$ a coor from its set $C(i,j)$ such that the colors in each row and each column are distinct?

$\endgroup$
2
$\begingroup$

Gil Kalai has a brief writeup here: http://gilkalai.wordpress.com/2012/04/26/galvins-proof-of-dinitzs-conjecture/

$\endgroup$
2
$\begingroup$

You can check out the chapter on Dinitz problem in Proofs from the Book.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.