Don't take life too seriously: it's just a temporary situation

Diniz (congettura di )

Congetture  Teoria dei grafi 

Dato un grafo G, si indica con ch’(G) il minimo numero tale che sia possibile colorare gli archi di G, in modo tale che non vi siano due archi dello stesso colore con un estremo in comune, se per ogni arco vi è una lista di almeno ch’(G) colori tra i quali scegliere.

 

Nel 1979 Jeffrey H. Dinitz propose la congettura che ch’(Kn, n) = n, dove Kn, n è un grafo bipartito completo con n vertici, ossia che è possibili colorare gli archi di un grafo Kn, n in modo tale che non vi siano due archi dello stesso colore con un estremo in comune se e solo se per ogni arco è disponibile una lista di almeno n colori diversi.

La congettura si può riformulare in termini di quadrati latini: data una matrice n × n è possibile assegnare a ogni elemento un simbolo, in modo che lo stesso simbolo non compaia due volte in ogni riga o colonna, se e solo se per ogni elemento è disponibile una lista di almeno n simboli diversi.

 

Nel 1994 Fred Galvin dimostrò che la congettura è vera.

 

La congettura è un caso speciale della congettura della colorazione degli archi con liste, tuttora non dimostrata.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.