Гипотеза Эрдёша — Дьярфаша (Inhkmy[g |j;~og — :,xjsgog)

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

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

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

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

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

История

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

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

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

Литература

• 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 года.