Erdős–Gyárfás-sejtés

A matematika megoldatlan problémája: Tartalmaz-e minden, 3 minimális fokszámú gráf olyan egyszerű kört, aminek hosszúsága kettő hatványa? (A matematika további megoldatlan problémái)

Markström-gráf
Markström az Erdős–Gyárfás-sejtés ellenpéldáinak számítógépes keresése során talált, 24 csúcsú, 3-reguláris síkbarajzolható gráfja, ami nem tartalmaz 4, illetve 8 hosszúságú köröket. A sejtést nem cáfolja, mivel 16 hosszúságú köröket viszont tartalmaz.
Csúcsok száma	24
Élek száma	36
Sugár	5
Átmérő	6
Derékbőség	3
Automorfizmusok	3

A matematika, azon belül a gráfelmélet területén az Erdős–Gyárfás-sejtés az 1995-ben Erdős Pál és Gyárfás András által megfogalmazott, bizonyítatlan állítás, mely szerint minden, legalább 3 minimális fokszámú gráf tartalmaz kettőhatvány hosszúságú egyszerű kört. Erdős 100 dollárt ajánlott a sejtés bizonyításáért, 50 dollárt egy ellenpéldáért; a sejtés Erdős számos sejtésének egyike.

Ha a sejtés hamis, az ellenpéldának olyan gráfnak kell lennie, melynek minimális fokszáma 3, és nem tartalmaz kettőhatvány hosszúságú kört. Gordon Royle és Klas Markström számítógépes kereséseiből tudjuk, hogy bármely ellenpéldának legalább 17 csúcsból kell állnia, egy 3-reguláris gráf esetén pedig legalább 30 csúcsból. Markström talál négy olyan, 24 csúcsú gráfot, melyben kizárólag 16 hosszú kettőhatvány-körök voltak. A négy gráf egyike síkbarajzolható; az Erdős–Gyárfás-sejtést azonban a 3-szorosan összefüggő, 3-reguláris síkbarajzolható gráfok esetére már sikerült belátni.(Heckman & Krakovski 2013)

Születtek gyengébb eredmények, melyek a gráf fokszámát és az elkerülhetetlen körhosszúságokat kapcsolják össze: létezik hosszúságok olyan S halmaza, ahol |S| = O(n^0,99), hogy minden 10 vagy magasabb átlagos fokszámú gráf tartalmaz S-ben lévő hosszúságú kört (Verstraëte 2005); (Sudakov & Verstraëte 2008) pedig felső korlátot ad a kettőhatvány hosszúságú kört nem tartalmazó, n csúcsú gráfok átlagos fokszámára: $e^{O(\log ^{*}n)}$, ahol log* a bináris iterált logaritmust jelenti. A sejtést (Daniel & Shauger 2001) igazolta síkbarajzolható karommentes gráfokra, (Shauger 1998) pedig olyan gráfokra, melyek nem tartalmaznak nagyméretű feszített csillagokat és néhány más, fokszámra vonatkozó követelménynek eleget tesznek.

Kapcsolódó kérdések

Vajon tartalmaz-e minden végtelen kromatikus számú gráf páratlan négyzetszám hosszúságú kört? Vajon minden, legalább 4 kromatikus számú gráf tartalmaz kettőhatványnál eggyel nagyobb hosszúságú kört?

Fordítás

• Ez a szócikk részben vagy egészben az Erdős–Gyárfás conjecture című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• 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, pp. 129–139.
• Heckman, Christopher Carl & Krakovski, Roi (2013), "Erdős-Gyárfás conjecture for cubic planar graphs", Electronic Journal of Combinatorics 20 (2): P7, <http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i2p7>.
• 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, pp. 61–65
• Sudakov, Benny & Verstraëte, Jacques (2008), "Cycle lengths in sparse graphs", Combinatorica 28 (3): 357–372, DOI 10.1007/s00493-008-2300-6.
• Verstraëte, Jacques (2005), "Unavoidable cycle lengths in graphs", Journal of Graph Theory 49 (2): 151–167, DOI 10.1002/jgt.20072.

További információk

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