thumb|right|200px|Markströmov kubični ravninski graf na 24-ih točkah brez ciklov dolžine 4 ali 8, najden z računalniških iskanjem za protiprimer Erdős-Gyárfásove domneve. Ima pa vseeno cikel s 16-imi (24) točkami.
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
Daniel in Shauger sta dokazala domnevo za ravninske grafe brez šap (brez zvezd s 3 povezavami).. Shauger je dokazal domnevo tudi za -proste grafe z najmanjšo stopnjo vsaj ali največjo stopnjo vsaj ..
Sklici
Viri
Zunanje povezave
Kategorija:Teorija grafov Kategorija:Nerešeni matematični problemi Kategorija:Paul Erdős Kategorija:1995 v znanosti