Congettura di Erdős-Gyárfás

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search
Il grafo planare cubico con 24 vertici di Markström privo di cicli di lunghezza 4 o 8, trovato durante una ricerca al computer per eventuali controesempi alla congettura di Erdős–Gyárfás

In teoria dei grafi, l'indimostrata congettura di Erdős–Gyárfás, proposta nel 1995 dal prolifico matematico Paul Erdős e il suo collaboratore András Gyárfás, afferma che ogni grafo con grado minimo 3 contiene un ciclo semplice la cui lunghezza è una potenza di 2. Erdős mise in palio $100 per la dimostrazione della congettura, o $50 per un controesempio.

Grazie alle ricerche al computer di Gordon Royle e Klas Markström, è noto che un eventuale controesempio deve avere almeno 17 vertici, e ogni controesempio cubico deve avere almeno 30 vertici. Le ricerche di Markström hanno consentito di trovare quattro grafi con 24 vertici in cui gli unici cicli di lunghezza pari ad una potenza di 2 hanno 16 vertici; uno di questi quattro grafi è planare.

Bibliografia[modifica | modifica wikitesto]

  • Shauger, Stephen E., Results on the Erdős–Gyárfás conjecture in K1,m-free graphs, Proc. 29th Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing, 1998, pp. 61–65.
  • Daniel, Dale and Shauger, Stephen E., A result on the Erdős–Gyárfás conjecture in planar graphs, Proc. 32nd Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing, 2001, pp. 129–139.

Collegamenti esterni[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica