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 Dinitz^[1] et démontré en 1994 par Fred Galvin^[2],[3].

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^[4] du graphe biparti complet ${\displaystyle K_{n,n}}$ est égal à ${\displaystyle n}$ . Autrement dit, si chaque arête du graphe biparti complet se voit attribuer un ensemble de ${\displaystyle 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ésultat^[2] 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 chromatique^[5]. Le théorème de Dinitz est également lié à la conjecture de la base de Rota (en)^[6].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Dinitz conjecture » (voir la liste des auteurs).

• Portail des mathématiques
• Portail de l'informatique théorique