En combinatoria , el teorema de Dinitz (antes conocido como conjetura de Dinitz ) es una afirmación sobre la extensión de matrices a cuadrados latinos parciales , propuesta en 1979 por Jeff Dinitz , [1] y demostrada en 1994 por Fred Galvin . [2] [3]
El teorema de Dinitz es que dado un arreglo cuadrado n × n , un conjunto de m símbolos con m ≥ n , y para cada celda del arreglo un conjunto de n elementos extraído 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 un resultado en la teoría de grafos , que el índice cromático de la lista del grafo bipartito completo es igual a . Es decir, si a cada borde del grafo bipartito completo se le asigna un conjunto de colores, es posible elegir uno de los colores asignados para cada borde de tal manera que no haya dos bordes incidentes al mismo vértice que tengan el mismo color.
La prueba 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 de coloración de la lista de aristas afirma que lo mismo se aplica no solo a los grafos bipartitos, sino también a cualquier multigrafo sin bucles. Una conjetura aún más general afirma que el número cromático de la lista de grafos sin garras siempre es igual a su número cromático . [4] El teorema de Dinitz también está relacionado con la conjetura de la base de Rota . [5]
