Conjecture de Dinitz

En combinatoire, le théorème de Dinitz (connu sous le nom de conjecture de Dinitz avant sa démonstration) est un énoncé sur l'extension de tableaux à des carrés latins partiels, proposé en 1979 par Jeff DinitzModèle:Références multiples et démontré en 1994 par Fred GalvinModèle:Références multiples.

Le théorème de Dinitz dit que, étant donné un tableau carré n × n, un ensemble X de m symboles (les couleurs) avec m ≥ n et, pour chaque cellule du tableau, un ensemble de n éléments pris dans X , on peut affecter à chaque cellule l'un de ces éléments de telle sorte qu'aucune ligne ou colonne n'a d'occurrence d'un même symbole. Le théorème peut également être formulé comme résultat de théorie des graphes ; il dit que l'indice chromatique de liste du graphe biparti complet $K_{n,n}$ est égal à $n$ . Autrement dit, si chaque arête du graphe biparti complet se voit attribuer un ensemble de $n$ couleurs, il est possible de choisir l'une des couleurs attribuées à chaque arête de sorte que les arêtes incidentes à un même sommet sont toutes de couleurs différentes.

La preuve de Galvin généralise ce résultatModèle:Références multiples en affirmant que, pour chaque multigraphe biparti, l'indice chromatique de liste est égal à son indice chromatique. Une conjecture plus générale, dite de coloration d'arêtes par listes affirme qu'il en est de même non seulement pour les graphes bipartis, mais aussi pour tout multigraphe sans boucle. Une conjecture encore plus générale stipule que le nombre chromatique de liste des graphes sans griffes est toujours égal à leur nombre chromatiqueModèle:Références multiples. Le théorème de Dinitz est également lié à la Modèle:LienModèle:Références multiples.