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

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

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

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

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

История

Гипотеза сформулирована в 1995 году венгерскими математиками Палом Эрдёшем и Шаблон:Нп3.

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

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

Литература

• Шаблон:Статья
• Шаблон:Статья

Ссылки

• Шаблон:Cite web
• Шаблон:Cite web