Concept

# Dinitz conjecture

Summary
In combinatorics, the Dinitz theorem (formerly known as 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 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. It can also be formulated as a result in graph theory, that the list chromatic index of the complete bipartite graph K_{n, n} equals n. That is, if each edge of the complete bipartite graph is assigned a set of n colors, it is possible to choose one of the assigned colors for each edge such that no two edges incident to the same vertex have the same color. Galvin's proof generalizes to the statement that, for every bipartite multigr
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications

Related people

Related units