Teorema de Dinitz

En combinatòria, la teorema de Dinitz (anteriorment conegut com a conjectura de Dinitz) és una afirmació sobre l'extensió de matrius a quadrats llatins parcials, proposta en 1979 per Jeff Dinitz, i demostrada en 1994 per Fred Galvin.

Enunciat

La teorema de Dinitz establix que, donada una matriu quadrada de n × n, un conjunt de m símbols en m = n i, per a cada cela de la matriu, un conjunt de n elements extrets del conjunt de m símbols, és possible elegir una forma d'etiquetar cada cela en un d'eixos elements, de tal manera que cap fila o columna repetixca un símbol.

També es pot formular com a resultat en teoria de grafos, que l'índex de la llista cromàtica del grafo bipartito complet $K_{n,n}$ és igual a $n$. És dir, si a cada aresta del grafo bipartito complet se li assigna un conjunt de $n$ colors, és possible elegir un dels colors assignats per a cada aresta de tal manera que cap de les dos arestes incidents en el mateix vèrtiç tinga el mateix color.

Demostració

La demostració de Galvin es generalisa a l'afirmació de que, per a cada multigrafo bipartito, l'índex cromàtic de la llista és igual a la seua índex cromàtic. La conjectura més general, la conjectura de coloració de la llista d'arestes, establix que açò mateixa es complix no solament per a grafos bipartitos, sino també per a qualsevol multigrafo sense bucles. Una conjectura encara més general establix que el número de la llista cromàtica d'un gràfic sense garres sempre és igual a la seua coloració de grafos. La teorema de Dinitz també està relacionat en la conjectura de la base de Trencada.