In combinatorics, the Dinitz theorem, formerly known as the Dinitz conjecture, is a statement about the extension of arrays to partial Latin squares, proposed in 1979 by Jeff Dinitz,^[1] and proved in 1994 by Fred Galvin.^[2][3]

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]

Galvin's argument uses the notion of a kernel of a directed graph. A kernel of a digraph ${\displaystyle D}$ is a set ${\displaystyle K}$ of vertices that is independent (no arc joins two vertices of ${\displaystyle K}$) and absorbing (every vertex outside ${\displaystyle K}$ has an arc directed into ${\displaystyle K}$). The proof combines this with the following lemma, the kernel method.^[2][6]

Kernel lemma. Let ${\displaystyle D}$ be an orientation of a graph ${\displaystyle G}$ such that every induced subdigraph of ${\displaystyle D}$ has a kernel, and let ${\displaystyle L}$ be a list assignment (on the vertices) with ${\displaystyle |L(v)|\geq d_{D}^{+}(v)+1}$ for every vertex ${\displaystyle v}$, where ${\displaystyle d_{D}^{+}(v)}$ is the out-degree of ${\displaystyle v}$. Then ${\displaystyle G}$ has a proper ${\displaystyle L}$-coloring.

The lemma is proved by induction: choose a color ${\displaystyle c}$ appearing in some list, let ${\displaystyle A}$ be the set of vertices whose lists contain ${\displaystyle c}$, take a kernel ${\displaystyle K}$ of the subdigraph induced on ${\displaystyle A}$, color the vertices of ${\displaystyle K}$ with ${\displaystyle c}$, and delete ${\displaystyle K}$ from the graph together with ${\displaystyle c}$ from all remaining lists. Every vertex of ${\displaystyle A\setminus K}$ loses at least one out-neighbor, so the out-degree condition is preserved and induction applies.^[6]

To apply this to ${\displaystyle L(K_{n,n})}$, whose vertices are the ${\displaystyle n^{2}}$ cells ${\displaystyle (i,j)}$, fix a reference Latin square that assigns to cell ${\displaystyle (i,j)}$ a symbol ${\displaystyle \sigma (i,j)\in \{1,\dots ,n\}}$. Orient the line graph as follows: for two cells in the same row, direct the arc from the smaller reference symbol to the larger; for two cells in the same column, direct it from the larger to the smaller. Because the symbols in each row and each column form a permutation of ${\displaystyle \{1,\dots ,n\}}$, the cell ${\displaystyle (i,j)}$ with ${\displaystyle \sigma (i,j)=s}$ has exactly ${\displaystyle n-s}$ out-arcs within its row and ${\displaystyle s-1}$ within its column, giving out-degree

${\displaystyle d^{+}(i,j)=(n-s)+(s-1)=n-1}$

for every cell. Lists of size ${\displaystyle n=(n-1)+1}$ thus satisfy the hypothesis of the kernel lemma.

Finally, every induced subdigraph has a kernel: a set of cells corresponds to a bipartite graph between rows and columns, and interpreting the reference symbols as preference rankings turns a kernel into a stable matching, which exists by the Gale–Shapley theorem. Hence ${\displaystyle K_{n,n}}$ is ${\displaystyle n}$-edge-choosable.^[2][7][6]

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]

• Weisstein, Eric W. "Dinitz Problem". MathWorld.