Editing Dinitz conjecture

{{Short description|Theorem in combinatorics}}
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]],{{r|ert}} and proved in 1994 by [[Fred Galvin]].{{r|g|z}}

The Dinitz theorem is that given an ''n'' &times; ''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]] <math>K_{n, n}</math> equals <math>n</math>. That is, if each edge of the complete bipartite graph is assigned a set of <math>n</math> 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 coloring|list chromatic number]] of [[claw-free graph]]s always equals their [[chromatic number]].{{r|gm}} The Dinitz theorem is also related to [[Rota's basis conjecture]].{{r|c}}

==References==
{{reflist|refs=

<ref name=ert>{{cite conference|last1=Erdős|first1=P.|author1-link=Paul Erdős|last2=Rubin|first2=A. L.|author2-link=Arthur Rubin|last3=Taylor|first3=H.|year=1979|url=http://www.math-inst.hu/~p_erdos/1980-07.pdf|contribution=Choosability in graphs|title=Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata|series=Congressus Numerantium|volume=26|pages=125–157|access-date=2017-04-22|archive-url=https://web.archive.org/web/20160309235325/http://www.math-inst.hu/~p_erdos/1980-07.pdf|archive-date=2016-03-09|url-status=dead}}</ref>

<ref name=c>{{cite journal |last=Chow |first=T. Y. |year=1995 |title=On the Dinitz conjecture and related conjectures |journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] |volume=145 |issue=1–3 |pages=73–82 |url=http://math.mit.edu/~tchow/dinitz.pdf |doi=10.1016/0012-365X(94)00055-N |doi-access=free }}</ref>

<ref name=g>{{cite journal | author=F. Galvin | author-link=Fred Galvin | title=The list chromatic index of a bipartite multigraph |journal=[[Journal of Combinatorial Theory]] |series=Series B |volume=63 |issue=1 |year=1995 |pages=153–158 |doi=10.1006/jctb.1995.1011|doi-access=free }}</ref>

<ref name=gm>{{cite journal | last1 = Gravier | first1 = Sylvain | last2 = Maffray | first2 = Frédéric | doi = 10.1016/S0012-365X(03)00292-9 | issue = 1–3 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]] | mr = 2046636 | pages = 211–218 | title = On the choice number of claw-free perfect graphs | volume = 276 | year = 2004| doi-access = free }}</ref>

<ref name=z>{{cite journal |last=Zeilberger |first=D. |author-link=Doron Zeilberger |year=1996 |title=The method of undetermined generalization and specialization illustrated with Fred Galvin's amazing proof of the Dinitz conjecture |journal=[[American Mathematical Monthly]] |volume=103 |issue=3 |pages=233–239 |arxiv=math/9506215 |doi=10.2307/2975373|jstor=2975373 }}</ref>

}}

==External links==
* {{MathWorld|title=Dinitz Problem|urlname=DinitzProblem}}

[[Category:Combinatorics]]
[[Category:Latin squares]]
[[Category:Graph coloring]]
[[Category:Theorems in discrete mathematics]]
[[Category:Conjectures]]
[[Category:Conjectures that have been proved]]


{{graph-stub}}