Dinitz theorem

The Dinitz theorem states that, given an ${\displaystyle n\times n}$ square array, a set of ${\displaystyle m}$ symbols with ${\displaystyle m\geq n}$, and for each cell of the array an ${\displaystyle n}$-element set drawn from the pool of ${\displaystyle m}$ symbols, it is possible to label each cell with one of the elements of its set in such a way that no symbol is repeated within any row or any column. The resulting array is a partial Latin square: if all the cell sets happen to be the same set of ${\displaystyle n}$ symbols, the labeling is an ordinary ${\displaystyle n\times n}$ Latin square.^[4]

The theorem is most naturally expressed in the language of list coloring. For a graph ${\displaystyle G}$, a list assignment ${\displaystyle L}$ attaches to every edge ${\displaystyle e}$ a set ${\displaystyle L(e)}$ of permitted colors; a proper ${\displaystyle L}$-edge-coloring assigns to each edge a color from its own list so that adjacent edges (those sharing an endpoint) receive distinct colors. The list chromatic index ${\displaystyle \chi '_{\ell }(G)}$ is the least integer ${\displaystyle k}$ such that a proper ${\displaystyle L}$-edge-coloring exists for every list assignment with ${\displaystyle |L(e)|\geq k}$ for all edges ${\displaystyle e}$. Since one may always take identical lists, ${\displaystyle \chi '_{\ell }(G)\geq \chi '(G)\geq \Delta (G)}$, where ${\displaystyle \chi '}$ is the ordinary chromatic index and ${\displaystyle \Delta }$ the maximum degree.

An ${\displaystyle n\times n}$ Latin square corresponds to a proper edge coloring of the complete bipartite graph ${\displaystyle K_{n,n}}$ with ${\displaystyle n}$ colors: the two vertex classes are the rows and the columns, the edge joining row ${\displaystyle i}$ to column ${\displaystyle j}$ represents the cell ${\displaystyle (i,j)}$, and its color is the symbol placed in that cell. Under this correspondence, prescribing an ${\displaystyle n}$-element list for each cell is exactly prescribing an ${\displaystyle n}$-element list for each edge. The Dinitz theorem is therefore the statement that

${\displaystyle \chi '_{\ell }(K_{n,n})=n.}$

Because ${\displaystyle \Delta (K_{n,n})=n}$, this asserts that the list chromatic index of ${\displaystyle K_{n,n}}$ attains its smallest possible value.^[4][3]

Galvin proved a considerably more general result: for every bipartite multigraph ${\displaystyle G}$,

${\displaystyle \chi '_{\ell }(G)=\chi '(G).}$

By Kőnig's edge-coloring theorem the chromatic index of a bipartite multigraph equals its maximum degree, so ${\displaystyle \chi '_{\ell }(G)=\Delta (G)}$. Taking ${\displaystyle G=K_{n,n}}$ recovers the Dinitz theorem.^[2][5]

Dinitz posed the problem in 1979, and it circulated for over a decade as one of the best-known open questions on list coloring.^[1][4] Partial results preceded Galvin's solution: Jeannette Janssen proved the statement for ${\displaystyle (n-1)\times n}$ rectangular arrays, and for the square case with lists of size ${\displaystyle n+1}$, by applying the polynomial method of Alon and Tarsi.^[8] Galvin settled the full conjecture in 1994 (published 1995) with the kernel argument above, which is elementary and self-contained.^[2] Expository accounts were given by Zeilberger^[3] and in the textbook literature.^[6][9]

Galvin's proof extends verbatim from ${\displaystyle K_{n,n}}$ to all bipartite multigraphs, and more generally to line-perfect graphs by way of Maffray's characterization of the line graphs possessing kernels.^[10] Alexandr Kostochka, Borodin, and Woodall strengthened the bipartite result by allowing shorter lists: for a bipartite graph ${\displaystyle G}$, a proper edge coloring exists whenever each edge ${\displaystyle uv}$ is given a list of size at least ${\displaystyle \max\{d_{G}(u),d_{G}(v)\}}$.^[5]

The list edge-coloring conjecture (or list coloring conjecture) asserts that ${\displaystyle \chi '_{\ell }(G)=\chi '(G)}$ for every loopless multigraph, not just bipartite ones; it remains open in general. An even more general conjecture states that the list chromatic number of every claw-free graph equals its chromatic number.^[11] The Dinitz theorem is also related to Rota's basis conjecture.^[4]