Гипотеза Дьярфаса – Самнера - Gyárfás–Sumner conjecture

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Приводит ли запрет дерева и клики в качестве индуцированных подграфов к графам с ограниченным хроматическим числом?
(больше нерешенных задач по математике)

В теория графов, то Гипотеза Дьярфаса – Самнера спрашивает, для каждого ли дерево и полный график , графики без ни в качестве индуцированные подграфы возможно правильно окрашенный используя только постоянное количество цветов. Точно так же он спрашивает, есть ли -свободные графы -ограниченный.[1]Он назван в честь Андраш Дьярфас и Дэвид Самнер, которые сформулировали его независимо в 1975 и 1981 годах соответственно.[2][3] Остается недоказанным.[4]

В этой гипотезе нельзя заменить графом с циклами. В качестве Пол Эрдёш и Андраш Хайнал показали, что существуют графы без треугольников с сколь угодно большим хроматическим числом и в то же время сколь угодно большим обхват.[5] Используя эти графы, можно получить графы, которые избегают любого фиксированного выбора циклического графа и клики (с более чем двумя вершинами) в качестве индуцированных подграфов и превышают любую фиксированную границу хроматического числа.[1]

Гипотеза, как известно, верна для некоторых специальных вариантов выбора , включая пути,[6] звезды, и деревья радиуса два.[7]Также известно, что для любого дерева , графы, не содержащие подразделение из находятся -ограниченный.[1]

Рекомендации

  1. ^ а б c Скотт, А. Д. (1997), "Индуцированные деревья в графах с большим хроматическим числом", Журнал теории графов, 24 (4): 297–311, Дои:10.1002 / (SICI) 1097-0118 (199704) 24: 4 <297 :: AID-JGT2> 3.3.CO; 2-X, МИСТЕР  1437291
  2. ^ Дьярфаш, А. (1975), "О накрывающих числах Рамсея", Бесконечные и конечные множества (Colloq., Keszthely, 1973; посвящается П. Эрдёшу в день его 60-летия), Vol. II, Коллок. Математика. Soc. Янош Бойяи, 10, Амстердам: Северная Голландия, стр. 801–816, МИСТЕР  0382051
  3. ^ Самнер, Д. П. (1981), "Поддеревья графа и хроматическое число", Теория и приложения графов (Kalamazoo, Mich., 1980), Wiley, New York, стр. 557–576, МИСТЕР  0634555
  4. ^ Чудновский, Мария; Сеймур, Пол (2014), «Расширение гипотезы Дьярфаса-Самнера», Журнал комбинаторной теории, Серия B, 105: 11–16, Дои:10.1016 / j.jctb.2013.11.002, МИСТЕР  3171779
  5. ^ Эрдеш, П.; Хайнал, А. (1966), «О хроматическом числе графов и систем множеств» (PDF), Acta Mathematica Academiae Scientiarum Hungaricae, 17: 61–99, Дои:10.1007 / BF02020444, МИСТЕР  0193025
  6. ^ Дьярфаш, А. (1987), "Проблемы из мира, окружающего совершенные графы", Труды Международной конференции по комбинаторному анализу и его приложениям (Pokrzywna, 1985), Застосования Математики, 19 (3–4): 413–441 (1988), МИСТЕР  0951359
  7. ^ Kierstead, H.A .; Пенрис, С. Г. (1994), "Деревья радиуса два определяют χ-ограниченные классы", Журнал теории графов, 18 (2): 119–129, Дои:10.1002 / jgt.3190180203, МИСТЕР  1258244

внешняя ссылка