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, and proved in 1994 by Fred Galvin.

Statement

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 Latin square.

Formulation as list edge coloring

The theorem is most naturally expressed in the language of list coloring. For a graph, a list assignment of permitted colors; a -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 is the ordinary chromatic index the maximum degree.

Latin square corresponds to a proper edge coloring of the complete bipartite graph-element list for each edge. The Dinitz theorem is therefore the statement that

attains its smallest possible value.

Galvin's theorem

Galvin proved a considerably more general result: for every bipartite multigraph,

By Kőnig's edge-coloring theorem recovers the Dinitz theorem.

Proof via kernels

Galvin's argument uses the notion of a kernel of vertices that is independent) and absorbing). The proof combines this with the following lemma, the kernel method.

Kernel lemma. is the out-degree-coloring.

loses at least one out-neighbor, so the out-degree condition is preserved and induction applies.

within its column, giving out-degree

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-edge-choosable.

History

Dinitz posed the problem in 1979, and it circulated for over a decade as one of the best-known open questions on list coloring. Partial results preceded Galvin's solution: Jeannette Janssen, by applying the polynomial method of Alon and Tarsi. Galvin settled the full conjecture in 1994 (published 1995) with the kernel argument above, which is elementary and self-contained. Expository accounts were given by Zeilberger and in the textbook literature.

Generalizations

to all bipartite multigraphs, and more generally to line-perfect graphs by way of Maffray's characterization of the line graphs possessing kernels. Alexandr Kostochka.

The list edge-coloring conjecture 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. The Dinitz theorem is also related to Rota's basis conjecture.

References

External links