χ -ограниченный

В теории графов $\chi$ - ограниченная семья ${\mathcal {F}}$ графов – это тот, для которого существует некоторая функция $f$ такая, что для любого целого числа $t$ графики в ${\mathcal {F}}$ с $t=\omega (G)$ ( номер клики ) можно раскрасить не более чем $f(t)$ цвета. Функция $f(t)$ называется $\chi$ -связывающая функция для ${\mathcal {F}}$ . Эти концепции и их обозначения были сформулированы Андрашем Дьярфасом . ^{[ 1 ]} Употребление греческой буквы хи в термине $\chi$ -ограниченный основан на том факте, что хроматическое число графа $G$ обычно обозначается $\chi (G)$ . Обзор местности можно найти в опросе Алекса Скотта и Пола Сеймура . ^{[ 2 ]}

Нетривиальность

Неверно, что семейство всех графов $\chi$ -ограниченный. Как показали Декарт (1947) , Зыков (1949) и Мысельский (1955) , существуют графы без треугольников сколь угодно большого хроматического числа: ^{[ 3 ]}^{[ 4 ]}^{[ 5 ]} поэтому для этих графиков невозможно определить конечное значение $f(2)$ . Таким образом, $\chi$ -ограниченность — нетривиальная концепция, верная для некоторых семейств графов и ложная для других. ^{[ 6 ]}

Конкретные классы

Каждый класс графов ограниченного хроматического числа (тривиально) $\chi$ -ограниченный, с $f(t)$ равна границе хроматического числа. Сюда входят, например, плоские графы , двудольные графы и графы ограниченного вырождения . Кроме того, графы, в которых число независимости ограничено, также являются $\chi$ -ограничены, поскольку из теоремы Рамсея следует, что они имеют большие клики.

Теорему Визинга можно интерпретировать как утверждение, что линейные графики $\chi$ -ограниченный, с $f(t)=t+1$ . ^{[ 7 ]}^{[ 8 ]} Графы без когтей в более общем плане также $\chi$ - ограничен с $f(t)\leq t^{2}$ . В этом можно убедиться, используя теорему Рэмси, чтобы показать, что в этих графах вершина со многими соседями должна быть частью большой клики. В худшем случае эта граница почти точна, но связные графы без клешней, включающие три взаимно несмежные вершины, имеют еще меньшее хроматическое число. $f(t)=2t$ . ^{[ 7 ]}

Другой $\chi$ -ограниченные семейства графов включают:

Идеальные графики , с $f(t)=t$
Графики коробочности два ^{[ 9 ]}, который представляет собой графики пересечения прямоугольников, параллельных осям, с $f(t)\in O(t\log(t))$ ( большая буква О ) ^{[ 10 ]}
Графы ограниченной кликовой ширины ^{[ 11 ]}
Графы пересечения масштабированных и переведенных копий любой компактной выпуклой формы на плоскости. ^{[ 12 ]}
Многоугольно -круговые графики , с $f(t)=2^{t}$
Круговые графики , с $f(t)=2t\log _{2}t+2\log _{2}\log _{2}t+10t$ ^{[ 13 ]} и (обобщающие круговые графы) «графы внешних струн», графы пересечений ограниченных кривых на плоскости, которые все касаются неограниченной грани расположения кривых . ^{[ 14 ]}
Граф внешних струн — это граф пересечений кривых, лежащих в общей полуплоскости и имеющих одну конечную точку на границе этой полуплоскости. ^{[ 15 ]}
Графики пересечения кривых, пересекающих фиксированную кривую между 1 и $n\in \mathbb {N}$ раз ^{[ 16 ]}
Графы без четных дырок с $f(t)=2t$ , так как в каждом таком графе есть вершина, окрестность которой является объединением двух клик ^{[ 17 ]}

Однако, хотя графы пересечений выпуклых форм, круговые графы и графы внешних струн являются частными случаями струнных графов , сами струнные графы не являются таковыми. $\chi$ -ограниченный. К ним относятся как частный случай графы пересечений отрезков прямых , которые также не являются $\chi$ -ограниченный. ^{[ 6 ]}

Нерешенные проблемы

Нерешенная задача по математике :

Все ли классы графов без деревьев?

\chi

-ограниченный?

(еще нерешенные задачи по математике)

Согласно гипотезе Дьярфаса–Самнера , для любого дерева $T$ , графы, не содержащие $T$ в качестве подграфа индуцированного $\chi$ -ограниченный. Например, это будет включать в себя случай графов без когтей, поскольку коготь — это особый вид дерева. Однако известно, что гипотеза верна только для некоторых специальных деревьев, в том числе для путей ^{[ 1 ]} и деревья радиуса два. ^{[ 18 ]}

А $\chi$ -ограниченный класс графов полиномиально $\chi$ -ограничен, если он имеет $\chi$ -связывающая функция $f(t)$ растет не более чем полиномиально в зависимости от $t$ . Как каждый $n$ -вершинный граф $G$ содержит независимое множество мощности не менее $n/\chi (G)$ , все полиномиально $\chi$ -ограниченные классы обладают свойством Эрдеша–Хайнала . Еще одна проблема на $\chi$ -ограниченность была сформулирована Луи Эспере, который задался вопросом, каждый ли наследственный класс графов, $\chi$ -ограничен также полиномиально $\chi$ -ограниченный. ^{[ 8 ]} Сильный контрпример гипотезе Эспере был предложен в 2022 году Брянским, Дэвисом и Вальчаком, которые доказали, что существуют $\chi$ -ограниченные наследственные классы, функция которых $f(t)$ может быть выбрано произвольно, если оно растет быстрее, чем некоторый кубический полином. ^{[ 19 ]}

Ссылки

^ Jump up to: ^а ^б Дьярфас, А. (1987), «Проблемы из мира, окружающего идеальные графы» (PDF) , Труды Международной конференции по комбинаторному анализу и его приложениям (Pokrzywna, 1985), Zastosowania Matematyki , 19 (3–4): 413– 441 (1988), МР 0951359
^ Скотт, Алекс; Сеймур, Пол (2020), «Обзор $\chi$ -ограниченность», Журнал теории графов , 95 (3): 473–504, MR 4174126.
^ Декарт, Бланш (1947), «Задача трёх цветов», Эврика , 21.
^ Zykov, A. A. (1949), "О некоторых свойствах линейных комплексов" [On some properties of linear complexes], Mat. Sbornik , New Series (in Russian), 24 (66): 163–188, MR 0035428 . Translated into English in Amer. Math. Soc. Translation , 1952, MR 0051516 . Как цитирует Павлик и др. (2014)
^ Мисельский, Ян (1955), «Sur le coloriage desgraphs», Colloq. Математика. (на французском языке), 3 (2): 161–162, doi : 10,4064/см-3-2-161-162 , MR 0069494
^ Jump up to: ^а ^б Павлик, Аркадиуш; Козик, Якуб; Кравчик, Томаш; Ласонь, Михал; Мичек, Петр; Троттер, Уильям Т .; Вальчак, Бартош (2014), «Графы пересечений отрезков прямых с большим хроматическим числом без треугольников», Журнал комбинаторной теории, серия B , 105 : 6–10, arXiv : 1209.1595 , doi : 10.1016/j.jctb.2013.11. 001 , МР 3171778 , S2CID 9705484
^ Jump up to: ^а ^б Чудновская Мария ; Сеймур, Пол (2010), «Графы без клешней VI. Раскраска», Журнал комбинаторной теории, серия B , 100 (6): 560–572, doi : 10.1016/j.jctb.2010.04.005 , MR 2718677
^ Jump up to: ^а ^б Картик, Т.; Маффрэ, Фредерик (2016), «Оценка Визинга для хроматического числа в некоторых классах графов», Graphs and Combinatorics , 32 (4): 1447–1460, doi : 10.1007/s00373-015-1651-1 , MR 3514976 , S2CID 41279514
^ Асплунд, Э.; Грюнбаум, Б. (1960), «О проблеме раскраски», Mathematica Scandinavica , 8 : 181–188, doi : 10.7146/math.scand.a-10607 , MR 0144334
^ Чалермсук; Вальчак (2020), «Раскраска и независимый от максимального веса набор прямоугольников», arXiv : 2007.07880 [ cs.CG ]
^ Дворжак, Зденек; Краль, Даниэль (2012), «Классы графов с разложениями малого ранга $\chi$ -ограниченный», European Journal of Combinatorics , 33 (4): 679–683, arXiv : 1107.2161 , doi : 10.1016/j.ejc.2011.12.005 , MR 3350076 , S2CID 5530520
^ Ким, Сог-Джин; Косточка, Александр; Накпрасит, Киттикорн (2004), «О хроматическом числе графов пересечений выпуклых множеств на плоскости» , Электронный журнал комбинаторики , 11 (1), R52, doi : 10.37236/1805 , MR 2097318
^ Дэвис, Джеймс (2022), «Улучшенные границы для раскраски круговых графов», Proceedings of the American Mathematical Society , 150 (12): 5121–5135, arXiv : 2107.03585 , doi : 10.1090/proc/16044
^ Год, Александр; Вальчак, Бартош (2014), «Графы внешних струн $\chi$ -ограниченный», Труды Тридцатого ежегодного симпозиума по вычислительной геометрии (SoCG'14) , Нью-Йорк: ACM, стр. 136–143, doi : 10.1145/2582112.2582115 , MR 3382292 , S2CID 33362942
^ Рок, Александр; Вальчак, Бартош (2019), «Графы внешних строк χ-ограничены» , SIAM Journal on Discrete Mathematics , 33 (4): 2181–2199, arXiv : 1312.1559 , doi : 10.1137/17M1157374 , S2CID 9474387
^ Рок, Александр; Вальчак, Бартош (2019), «Кривые раскраски, пересекающие фиксированную кривую», Дискретная и вычислительная геометрия , 61 (4): 830–851, arXiv : 1512.06112 , doi : 10.1007/s00454-018-0031-z , S2CID 124706442
^ Чудновская Мария ; Сеймур, Пол (2023), «Графы без четных дырок все еще имеют бисимплициальные вершины», Journal of Combinatorial Theory, Series B , 161 : 331–381, arXiv : 1909.10967 , doi : 10.1016/j.jctb.2023.02.009 , МИСТЕР 4568110
^ Кирстед, штат ХА; Пенрис, С.Г. (1994), «Радиус двух деревьев определяет $\chi$ -ограниченные классы», Journal of The Graph Theory , 18 (2): 119–129, doi : 10.1002/jgt.3190180203 , MR 1258244
^ Брянски, Марцин; Дэвис, Джеймс; Вальчак, Бартош (2023), «Разделяющий полином $\chi$ -ограниченность от $\chi$ -ограниченность", Combinatorica , arXiv : 2201.08814 , doi : 10.1007/s00493-023-00054-3 , S2CID 246476859

Внешние ссылки

ограниченный Ци Открытый проблемный сад,

[g87-1] Jump up to: ^а ^б Дьярфас, А. (1987), «Проблемы из мира, окружающего идеальные графы» (PDF) , Труды Международной конференции по комбинаторному анализу и его приложениям (Pokrzywna, 1985), Zastosowania Matematyki , 19 (3–4): 413– 441 (1988), МР 0951359

[survey-2] Скотт, Алекс; Сеймур, Пол (2020), «Обзор $\chi$ -ограниченность», Журнал теории графов , 95 (3): 473–504, MR 4174126.

[descartes-3] Декарт, Бланш (1947), «Задача трёх цветов», Эврика , 21.

[z-4] Zykov, A. A. (1949), "О некоторых свойствах линейных комплексов" [On some properties of linear complexes], Mat. Sbornik , New Series (in Russian), 24 (66): 163–188, MR 0035428 . Translated into English in Amer. Math. Soc. Translation , 1952, MR 0051516 . Как цитирует Павлик и др. (2014)

[m-5] Мисельский, Ян (1955), «Sur le coloriage desgraphs», Colloq. Математика. (на французском языке), 3 (2): 161–162, doi : 10,4064/см-3-2-161-162 , MR 0069494

[pkk-6] Jump up to: ^а ^б Павлик, Аркадиуш; Козик, Якуб; Кравчик, Томаш; Ласонь, Михал; Мичек, Петр; Троттер, Уильям Т .; Вальчак, Бартош (2014), «Графы пересечений отрезков прямых с большим хроматическим числом без треугольников», Журнал комбинаторной теории, серия B , 105 : 6–10, arXiv : 1209.1595 , doi : 10.1016/j.jctb.2013.11. 001 , МР 3171778 , S2CID 9705484

[cs-7] Jump up to: ^а ^б Чудновская Мария ; Сеймур, Пол (2010), «Графы без клешней VI. Раскраска», Журнал комбинаторной теории, серия B , 100 (6): 560–572, doi : 10.1016/j.jctb.2010.04.005 , MR 2718677

[km-8] Jump up to: ^а ^б Картик, Т.; Маффрэ, Фредерик (2016), «Оценка Визинга для хроматического числа в некоторых классах графов», Graphs and Combinatorics , 32 (4): 1447–1460, doi : 10.1007/s00373-015-1651-1 , MR 3514976 , S2CID 41279514

[ag60-9] Асплунд, Э.; Грюнбаум, Б. (1960), «О проблеме раскраски», Mathematica Scandinavica , 8 : 181–188, doi : 10.7146/math.scand.a-10607 , MR 0144334

[max-10] Чалермсук; Вальчак (2020), «Раскраска и независимый от максимального веса набор прямоугольников», arXiv : 2007.07880 [ cs.CG ]

[dk12-11] Дворжак, Зденек; Краль, Даниэль (2012), «Классы графов с разложениями малого ранга $\chi$ -ограниченный», European Journal of Combinatorics , 33 (4): 679–683, arXiv : 1107.2161 , doi : 10.1016/j.ejc.2011.12.005 , MR 3350076 , S2CID 5530520

[kkn04-12] Ким, Сог-Джин; Косточка, Александр; Накпрасит, Киттикорн (2004), «О хроматическом числе графов пересечений выпуклых множеств на плоскости» , Электронный журнал комбинаторики , 11 (1), R52, doi : 10.37236/1805 , MR 2097318

[circ-13] Дэвис, Джеймс (2022), «Улучшенные границы для раскраски круговых графов», Proceedings of the American Mathematical Society , 150 (12): 5121–5135, arXiv : 2107.03585 , doi : 10.1090/proc/16044

[rw14-14] Год, Александр; Вальчак, Бартош (2014), «Графы внешних струн $\chi$ -ограниченный», Труды Тридцатого ежегодного симпозиума по вычислительной геометрии (SoCG'14) , Нью-Йорк: ACM, стр. 136–143, doi : 10.1145/2582112.2582115 , MR 3382292 , S2CID 33362942

[outer-15] Рок, Александр; Вальчак, Бартош (2019), «Графы внешних строк χ-ограничены» , SIAM Journal on Discrete Mathematics , 33 (4): 2181–2199, arXiv : 1312.1559 , doi : 10.1137/17M1157374 , S2CID 9474387

[curv-16] Рок, Александр; Вальчак, Бартош (2019), «Кривые раскраски, пересекающие фиксированную кривую», Дискретная и вычислительная геометрия , 61 (4): 830–851, arXiv : 1512.06112 , doi : 10.1007/s00454-018-0031-z , S2CID 124706442

[evenhole-17] Чудновская Мария ; Сеймур, Пол (2023), «Графы без четных дырок все еще имеют бисимплициальные вершины», Journal of Combinatorial Theory, Series B , 161 : 331–381, arXiv : 1909.10967 , doi : 10.1016/j.jctb.2023.02.009 , МИСТЕР 4568110

[kp94-18] Кирстед, штат ХА; Пенрис, С.Г. (1994), «Радиус двух деревьев определяет $\chi$ -ограниченные классы», Journal of The Graph Theory , 18 (2): 119–129, doi : 10.1002/jgt.3190180203 , MR 1258244

[bdw-19] Брянски, Марцин; Дэвис, Джеймс; Вальчак, Бартош (2023), «Разделяющий полином $\chi$ -ограниченность от $\chi$ -ограниченность", Combinatorica , arXiv : 2201.08814 , doi : 10.1007/s00493-023-00054-3 , S2CID 246476859

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]