Conjectura Erdős-Gyárfás
În teoria graficelor , conjectura nedovedită Erdős - Gyárfás , propusă în 1995 de matematicianul prolific Paul Erdős și colaboratorul său András Gyárfás , afirmă că fiecare grafic cu grad minim 3 conține un ciclu simplu a cărui lungime este o putere de 2. Erdős a oferit $ 100 pentru dovada conjecturii sau 50 $ pentru un contraexemplu.
Datorită cercetărilor informatice efectuate de Gordon Royle și Klas Markström , se știe că orice contraexemplu trebuie să aibă cel puțin 17 vârfuri și fiecare contraexemplu cubic trebuie să aibă cel puțin 30 de vârfuri. Cercetările lui Markström au permis găsirea a patru grafice cu 24 de vârfuri în care singurele cicluri de lungime egale cu o putere de 2 au 16 vârfuri; unul dintre aceste patru grafice este plan .
Bibliografie
- Markström, Klas, Grafice extreme pentru unele probleme pe cicluri în grafice ( PDF ), în Congr. Numerantium , vol. 171, 2004, pp. 179–192.
- Shauger, Stephen E., Rezultate despre conjectura Erdős - Gyárfás în K 1, m- grafice libere , Proc. 29th Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing , 1998, pp. 61–65.
- Daniel, Dale și Shauger, Stephen E., Un rezultat asupra conjecturii Erdős - Gyárfás în grafice plane , Proc. 32nd Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing , 2001, pp. 129–139.
linkuri externe
- ( EN ) Exoo, Geoffrey, Grafice fără cicluri de lungimi specificate , pe ginger.indstate.edu . Adus la 24 octombrie 2006 (arhivat din original la 17 martie 2013) .
