Erdős-Gyárfásova domneva
Erdős-Gyárfásova domneva je v teoriji grafov nedokazana domneva, ki sta jo leta 1995 podala Paul Erdős in njegov sodelavec András Gyárfás. Domneva pravi, da vsak graf s stopnjo vsaj 3 vsebuje enostavni cikel, katerega dolžina je potenca 2. Erdős je za dokaz domneve ponudil 100 $ in 50 $ za protiprimer.
Z računalniškim iskanjem Gordona Roylea in Klasa Markströma je znano, da mora imeti protiprimer vsaj 17 točk, vsak protiprimer s kubičnim grafom pa vsaj 30 točk. Markström je z iskanjem našel štiri grafe na 24-ih točkah, v katerih ima edini cikel z dolžino potence 2 16 točk. Eden od teh grafov je ravninski in hkrati tudi Hamiltonov.
Delni rezultati
urediDaniel in Shauger sta dokazala domnevo za ravninske grafe brez šap (brez zvezd s 3 povezavami).[1] Shauger je dokazal domnevo tudi za -proste grafe z najmanjšo stopnjo vsaj ali največjo stopnjo vsaj .[2]
Sklici
urediViri
uredi- Daniel, Dale; Shauger, Stephen E. (2001). »A result on the Erdős–Gyárfás conjecture in planar graphs«. Proc. 32nd Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing. str. 129–139.
- Markström, Klas (2004). »Extremal graphs for some problems on cycles in graphs« (PDF). Congr. Numerantium. Zv. 171. str. 179–192.
- Shauger, Stephen E. (1998). »Results on the Erdős–Gyárfás conjecture in K1,m-free graphs«. Proc. 29th Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing. str. 61–65.
Zunanje povezave
uredi- Exoo, Geoffrey. »Graphs Without Cycles of Specified Lengths« (v angleščini). Arhivirano iz prvotnega spletišča dne 5. februarja 2012. Pridobljeno 2. septembra 2010.
- West, Douglas B. »Erdős Gyárfás Conjecture on 2-power Cycle Lengths«. Open Problems - Graph Theory and Combinatorics (v angleščini).