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

Hajós (congettura di)

Congetture  Teoria dei grafi 

Il matematico ungherese György Hajós (Budapest, 21/2/1912 – Budapest, 17/3/1972) propose una versione più forte della congettura di Hadwiger: ogni grafo che richieda n colori per essere colorato in modo che non vi siano due nodi dello stesso colore collegati da un arco contiene una suddivisione di un grafo completo (un grafo nel quale ogni nodo è connesso a tutti gli altri) a n nodi. Una suddivisione di un grafo si ottiene inserendo nodi intermedi lungo gli archi (non necessariamente tutti).

 

La congettura è vera per n sino a 4, ma P.A: Catlin trovò nel 1979 controesempi per n ≥ 7; restano aperti quindi i casi n = 5 e n = 6.

Contattami

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