# Dinitz conjecture

In combinatorics, 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.

The Dinitz conjecture, now a theorem, is that given an *n* × *n* square array, a set of *m* symbols with *m* ≥ *n*, and for each cell of the array an *n*-element set drawn from the pool of *m* symbols, it is possible to choose a way of labeling each cell with one of those elements in such a way that no row or column repeats a symbol.

The Dinitz conjecture is closely related to graph theory, in which it can be succinctly stated as for natural . It means that the list chromatic index of the complete bipartite graph equals . In fact, Fred Galvin proved the Dinitz conjecture as a special case of his theorem stating that the list chromatic index of any bipartite multigraph is equal to its chromatic index. Moreover, it is also a special case of the **edge list coloring conjecture** saying that the same holds not only for bipartite graphs, but also for any loopless multigraph.

## References

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}