Гипотеза Эрдёша — Дьярфаша

Нерешённые проблемы математики: Содержит ли кубический граф простой цикл длиной, равной степени двойки?

Гипотеза Эрдёша — Дьярфаша — нерешённая проблема в теории графов

Граф Маркстрёма с 24 вершинами, являющийся кубическим планарным графом без циклов длины 4 и 8, найденный в процессе компьютерного поиска контрпримера гипотезе Эрдёша — Дьярфаша. Он имеет, однако, циклы длиной 16.

Формулировка

Любой граф с вершинами степени не менее 3 содержит простой цикл длиной, равной степени двойки.

История

Гипотеза сформулирована в 1995 году венгерскими математиками Палом Эрдёшем и Андрашем Дьярфашем^[англ.].

Компьютерный поиск, осуществлённый Гордоном Ройлом^[англ.] и Класом Маркстрёмом (Klas Markström) показал, что любой контрпример должен иметь минимум 17 вершин и любой кубический контрпример должен иметь минимум 30 вершин. Поиск Маркстрёма дал четыре графа с 24 вершинами, имеющих циклы степени двойки только с 16 вершинами, при этом один из этих графов является планарным.

Известен более слабый результат относительно степени графа, содержащего циклы длины из некоторого множества: имеется множество $S$ длин, с $|S|=\mathrm {O} (n^{0,99})$ , такое, что любой граф со средней степенью десять или более содержит цикл с длиной из $S$ ^[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 года.

[1] Jacques Verstraëte. Unavoidable cycle lengths in graphs // Journal of Graph Theory. — 2005. — Т. 49, вып. 2. — С. 151–167. — doi:10.1002/jgt.20072.

[2] Dale Daniel, Stephen E. Shauger. Proc. 32nd Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing. — 2001. — С. 129–139.

[3] Stephen E. Shauger. Proc. 29th Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing. — 1998. — С. 61–65.

[1]

[2]

[3]