El teorema de Dinitz establece que, dada una matriz cuadrada de n × n, un conjunto de m símbolos con m = n y, para cada celda de la matriz, un conjunto de n elementos extraídos del conjunto de m símbolos, es posible elegir una forma de etiquetar cada celda con uno de esos elementos, de tal manera que ninguna fila o columna repita un símbolo.

También se puede formular como resultado en teoría de grafos, que el índice de la lista cromática del grafo bipartito completo ${\displaystyle K_{n,n}}$  es igual a ${\displaystyle n}$ . Es decir, si a cada arista del grafo bipartito completo se le asigna un conjunto de ${\displaystyle n}$  colores, es posible elegir uno de los colores asignados para cada arista de tal manera que ninguna de las dos aristas incidentes en el mismo vértice tenga el mismo color.

La demostración de Galvin se generaliza a la afirmación de que, para cada multigrafo bipartito, el índice cromático de la lista es igual a su índice cromático. La conjetura más general, la conjetura de coloración de la lista de aristas, establece que esto mismo se cumple no solo para grafos bipartitos, sino también para cualquier multigrafo sin bucles. Una conjetura aún más general establece que el número de la lista cromática de un gráfico sin garras siempre es igual a su coloración de grafos.^[4]​ El teorema de Dinitz también está relacionado con la conjetura de la base de Rota.^[5]​

• Weisstein, Eric W. «Dinitz Problem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.