Congettura di Erdős-Gyárfás

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

• Markström, Klas, Extremal graphs for some problems on cycles in graphs (PDF), in Congr. Numerantium, vol. 171, 2004, pp. 179–192.

• Shauger, Stephen E., Results on the Erdős–Gyárfás conjecture in K_1,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

• (EN) Exoo, Geoffrey, Graphs Without Cycles of Specified Lengths, su ginger.indstate.edu. URL consultato il 24 ottobre 2006 (archiviato dall'url originale il 17 marzo 2013).

• (EN) West, Douglas B., Erdős Gyárfás Conjecture on 2-power Cycle Lengths, su Open Problems - Graph Theory and Combinatorics.