Erdős-Gyárfásova domneva

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 (2⁴) 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 $K_{1,m}$-proste grafe z najmanjšo stopnjo vsaj $m+1$ ali največjo stopnjo vsaj $2m-1$.

Viri

• 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: 129–139. 
• Markström, Klas (2004). "Extremal graphs for some problems on cycles in graphs". Congr. Numerantium 171: 179–192. http://abel.math.umu.se/~klasm/Uppsatser/cycex.pdf. 
• Shauger, Stephen E. (1998). "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: 61–65. 

Zunanje povezave

• Exoo, Geoffrey. Graphs Without Cycles of Specified Lengths (v angleščini).
• West, Douglas B.. Erdős Gyárfás Conjecture on 2-power Cycle Lengths (v angleščini). Open Problems - Graph Theory and Combinatorics.