Erdős–Gyárfás-sejtés
Sablon:Megoldatlan Sablon:Gráf infobox 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.Sablon:Harv
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(n0,99), hogy minden 10 vagy magasabb átlagos fokszámú gráf tartalmaz S-ben lévő hosszúságú kört Sablon:Harv; Sablon:Harv 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: , ahol log* a bináris iterált logaritmust jelenti. A sejtést Sablon:Harv igazolta síkbarajzolható karommentes gráfokra, Sablon:Harv 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?[1]
Fordítás
Jegyzetek
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation.
- Sablon:Citation
- Sablon:Citation.
- Sablon:Citation.
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
- ↑ P. Erdős, Some old and new problems in various branches of combinatorics. Graphs and combinatorics (Marseille, 1995). Discrete Math. 165/166 (1997), 227–231.