Dinitz conjecture
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 formula_1 equals formula_2. That is, if each edge of the complete bipartite graph is assigned a set of formula_2 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 multigraph, the list chromatic index equals its chromatic index. The more general edge list coloring conjecture states that the same holds not only for bipartite graphs, but also for any loopless multigraph. An even more general conjecture states that the list chromatic number of claw-free graphs always equals their chromatic number. The Dinitz theorem is also related to Rota's basis conjecture.
Q76592
combinatorics
Concept
Q679367
Latin squares
Concept
Q11007940
Jeff Dinitz
PER
Q5495217
Fred Galvin
PER
Q131476
graph theory
Concept
Q15300219
list chromatic index
Concept
Q913598
complete bipartite graph
Concept
Q2642629
multigraph
Concept
Q1050972
chromatic index
Concept
Q1130404
list chromatic number
Concept
Q5129750
claw-free graph
Concept
Q504843
chromatic number
Concept
Q7370200
Rota's basis conjecture
MISC
Q5278348
Dinitz conjecture
LOC
1979-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1979
DATE
1994-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1994
DATE
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
named after
field of work
studies