Гипотеза Эрдёша — Дьярфаша
Гипотеза Эрдёша — Дьярфаша — нерешённая проблема в теории графов
Формулировка
Любой граф с вершинами степени не менее 3 содержит простой цикл длиной, равной степени двойки.
История
Гипотеза сформулирована в 1995 году венгерскими математиками Палом Эрдёшем и Андрашем Дьярфашем .
Компьютерный поиск, осуществлённый Гордоном Ройлом и Класом Маркстрёмом (Klas Markström) показал, что любой контрпример должен иметь минимум 17 вершин и любой кубический контрпример должен иметь минимум 30 вершин. Поиск Маркстрёма дал четыре графа с 24 вершинами, имеющих циклы степени двойки только с 16 вершинами, при этом один из этих графов является планарным.
Известен более слабый результат относительно степени графа, содержащего циклы длины из некоторого множества: имеется множество [math]\displaystyle{ S }[/math] длин, с [math]\displaystyle{ |S|=\mathrm O (n^{0,99}) }[/math], такое, что любой граф со средней степенью десять или более содержит цикл с длиной из [math]\displaystyle{ S }[/math][1]. Известно также, что гипотеза верна для планарных графов без клешней[2] и для графов, у которых нет больших звёзд и которые удовлетворяют дополнительным ограничениям на степень вершин[3].
Примечания
- ↑ Jacques Verstraëte. Unavoidable cycle lengths in graphs // Journal of Graph Theory. — 2005. — Т. 49, вып. 2. — С. 151–167. — doi:10.1002/jgt.20072.
- ↑ Dale Daniel, Stephen E. Shauger. Proc. 32nd Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing. — 2001. — С. 129–139.
- ↑ Stephen E. Shauger. Proc. 29th Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing. — 1998. — С. 61–65.
Литература
- Extremal graphs for some problems on cycles in graphs // Congr. Numerantium. — 2004. — Т. 171. — С. 179–192.
- Benny Sudakov, Jacques Verstraëte. Cycle lengths in sparse graphs // Combinatorica. — 2008. — Т. 28. — С. 357–372. — doi:10.1007/s00493-008-2300-6. — arXiv:0707.2117.
Ссылки
- Exoo, Geoffrey. Graphs Without Cycles of Specified Lengths . Архивировано 17 марта 2013 года.
- West, Douglas B. Erdős Gyárfás Conjecture on 2-power Cycle Lengths . Open Problems - Graph Theory and Combinatorics. Архивировано 17 марта 2013 года.
Для улучшения этой статьи желательно: |