Меню
Главная
Случайная статья
Настройки
|
Гипотеза Эрдёша — Дьярфаша — нерешённая проблема в теории графов
Содержание
Формулировка
Любой граф с вершинами степени не менее 3 содержит простой цикл длиной, равной степени двойки.
История
Гипотеза сформулирована в 1995 году венгерскими математиками Палом Эрдёшем и Андрашем Дьярфашем[англ.].
Компьютерный поиск, осуществлённый Гордоном Ройлом[англ.] и Класом Маркстрёмом (Klas Markstrm) показал, что любой контрпример должен иметь минимум 17 вершин и любой кубический контрпример должен иметь минимум 30 вершин.
Поиск Маркстрёма дал четыре графа с 24 вершинами, имеющих циклы степени двойки только с 16 вершинами, при этом один из этих графов является планарным.
Известен более слабый результат относительно степени графа, содержащего циклы длины из некоторого множества: имеется множество длин, с , такое, что любой граф со средней степенью десять или более содержит цикл с длиной из [1]. Известно также, что гипотеза верна для планарных графов без клешней[2] и для графов, у которых нет больших звёзд и которые удовлетворяют дополнительным ограничениям на степень вершин[3].
Примечания
- Jacques Verstrate. 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.
-
Литература- Extremal graphs for some problems on cycles in graphs // Congr. Numerantium. — 2004. — Т. 171. — С. 179–192.
- Benny Sudakov, Jacques Verstrate. Cycle lengths in sparse graphs // Combinatorica. — 2008. — Т. 28. — С. 357–372. — doi:10.1007/s00493-008-2300-6. — arXiv:0707.2117.
Ссылки
|
|