Cuadrados latinos, coloración por listas y el problema de Dinitz

Autor: Enrique Casas Bautista
El desarrollo de la Teoría de gráficas ha utilizado, entre otras, muchas de las ideas propuestas para intentar resolver la conjetura de los cuatro colores, hoy en día la coloración sigue siendo un tema muy estudiado, en esta plática presentare un problema simple de coloración, planteado por Jeff Dinitz en 1978, que desafió todos los ataques por resolverlo hasta su solución quince años más tarde, debida a Fred Galvin. El problema dice lo siguiente: Consideremos un tablero cuadrado de nxn casillas. en cada casilla (i, j) se dispone de n colores del conjunto c(i, j). ¿Es posible colorear las casillas de forma que los colores de las casillas de cada fila y de cada columna sean distintos?