The Dinitz theorem, known before its 1994 proof by Fred Galvin as the Dinitz conjecture, concerns list edge-colorings of the complete bipartite graph K(n,n). It states that if every cell of an n by n array is assigned a set of n symbols drawn from at least n available symbols, each cell can be filled with a symbol from its own set so that no symbol repeats in any row or column, meaning the list chromatic index of K(n,n) equals n; Galvin's proof, using the notion of kernels of directed graphs, in fact establishes the result for all bipartite multigraphs, beyond the complete bipartite case Jeff Dinitz first conjectured in 1979. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Classification
Statement Form Connections
Has Statement Form
In Branch
Source Dinitz theorem (Wikipedia)
Sources
1. Dinitz theorem (Wikipedia)
Lead section
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.
In Branch: Combinatorics, Lead sentence
In combinatorics, the Dinitz theorem, formerly known as the Dinitz conjecture, is a statement about the extension of arrays to par
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.