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
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Source Dinitz theorem (Wikipedia)
Sources
1. Dinitz theorem (Wikipedia)
In Branch: Combinatorics, Lead sentenceQuote, 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
Reader 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.