conjetura de Dinitz
En combinatoria , el teorema de Dinitz (anteriormente conocido como conjetura de Dinitz ) es un enunciado sobre la extensión de arreglos a cuadrados latinos parciales , propuesto en 1979 por Jeff Dinitz , [1] y probado en 1994 por Fred Galvin . [2] [3]
El teorema de Dinitz es 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í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 resultado en teoría de grafos , que el índice cromático de lista del grafo bipartito completo es igual . 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 arista de manera que no haya dos aristas incidentes en el 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 de coloración de la lista de bordes más general establece que lo mismo se aplica no solo a los gráficos bipartitos, sino también a cualquier multigrafo sin bucles. Una conjetura aún más general establece que el número cromático de la lista de gráficos 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]