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

Albertson (congettura di)

Congetture  Teoria dei grafi 

Il numero cromatico χ(G), di un grafo G è il minimo numero di colori necessari per colorarne i nodi in modo che non ci siano archi tra due nodi dello stesso colore (v. anche congettura della colorazione totale dei grafi).

La congettura proposta da Michael O. Albertson nel 2007 afferma che tra tutti i grafi con numero cromatico n, il grafo completo Kn è quello che può essere disegnato col minimo numero di incroci.

Una formulazione equivalente è che se un grafo può essere tracciato con meno incroci di Kn, allora richiede meno di n colori.

Sono noti grafi diversi da Kn che richiedono n colori e non contengono Kn come sottografo.

 

Richard K. Guy dimostrò nel 1973 che bastano Limite superiore per il numero di incroci in un grafo completo con n nodi incroci per un grafo completo con n nodi e congetturò che questo sia il numero minimo di incroci richiesti per ogni valore di n (v. numero di incroci). La combinazione della congettura di Albertson e di quella di Guy sarebbe quindi l’affermazione che se un grafo ha un numero cromatico uguale a n, per tracciarlo sul piano servono almeno tanti incroci quanti indicati dalla formula.

 

La congettura è banalmente vera per n fino a 4; per n = 5 equivale al teorema dei 4 colori (v. problema dei quattro colori), dal quale segue anche che ogni grafo tracciabile con n incroci si può colorare con n + 4 colori.

 

Sulla congettura sono stati fatti alcuni progressi:

  • nel 2005 Bogdan Oporowski e David Zhao dimostrarono che ogni grafo tracciabile con al massimo 3 incroci che non contenga K6 si può colorare con non più di 5 colori;

  • M.O. Albertson, M. Heenehan, A. McDonough e J. Wise dimostrarono che se il numero di incroci non supera 6, anche il numero cromatico non supera 6;

  • nel 2009 M.O. Albertson, D.W. Cranston e J. Fox dimostrarono che la congettura è vera per grafi con χ(G) ≤ 12 e che il minimo controesempio, se esiste, ha meno di 4χ(G) nodi;

  • nel 2009 János Barát, Géza Tóth dimostrarono che la congettura è vera per grafi con χ(G) ≤ 16 e che il minimo controesempio, se esiste, ha meno di 3.57χ(G) nodi.

Contattami

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