В теории графов ,-ограниченная семья графиков - это тот, для которого существует некоторая функция такой, что для каждого целого числа графики в с участием ( кликовое число ) можно раскрасить не более чемцвета. Эту концепцию и ее обозначения сформулировал Андраш Дьярфаш . [1] Использование греческой буквы chi в термине-ограниченный основан на том, что хроматическое число графа обычно обозначается .
Нетривиальность
Неверно, что семейство всех графов -ограниченный. Как показали Зыков (1949) и Mycielski (1955) , существуют графы без треугольников с произвольно большим хроматическим числом [2] [3], поэтому для этих графов невозможно определить конечное значение. Таким образом,-ограниченность - нетривиальное понятие, верное для одних семейств графов и ложное для других. [4]
Конкретные классы
Каждый класс графов ограниченного хроматического числа (тривиально)-ограниченный, с равна границе хроматического числа. Сюда входят, например, планарные графы , двудольные графы и графы ограниченного вырождения . Дополнительно, графы, в которых число независимости ограничено, также-ограниченные, поскольку из теоремы Рамсея следует, что они имеют большие клики.
Теорема Визинга можно интерпретировать как утверждение о том , что линейные графики являются-ограниченный, с . [5] [6] В кулачковыми свободные графики в более общем плане также-ограничен с . Это можно увидеть, используя теорему Рамсея, чтобы показать, что в этих графах вершина с множеством соседей должна быть частью большой клики. В худшем случае эта граница почти точна, но связные графы без клешней, включающие три взаимно несмежные вершины, имеют еще меньшее хроматическое число,. [5]
Другой -ограниченные графы включают в себя:
- В прекрасных графиках , с
- Графики прямоугольности два [7] , которые представляют собой графики пересечений прямоугольников, параллельных осям, с( большая нотация O ) [8]
- Графы ограниченной ширины клики [9]
- В пересечения графиков масштабированных и переведенных копий любой компактной форме выпуклой в плоскости [10]
- На полигон-круг графов , с
- В круг графов , с[11] и (обобщающие круговые графы) «внешние струнные графы», графы пересечений ограниченных кривых на плоскости, которые все касаются неограниченной грани расположения кривых [12]
- Граф внешней струны - это граф пересечений кривых, лежащих в общей полуплоскости и имеющих один конец на границе этой полуплоскости [13].
- В пересечении графиков кривых , которые пересекают фиксированный кривые между 1 ираз [14]
Однако, хотя графы пересечений выпуклых форм, круговые графы и графы внешних струн являются частными случаями строковых графов , сами строковые графы не являются-ограниченный. Они включают как частный случай графы пересечений отрезков прямых , которые также не являются-ограниченный. [4]
Нерешенные проблемы
Все ли классы графов без деревьев -ограниченный?
Согласно гипотезе Дьярфаса – Самнера для каждого дерева , графы, не содержащие как индуцированные подграф являются-ограниченный. Например, это может включать случай графов без клешней, поскольку клешни - это особый вид дерева. Однако известно, что эта гипотеза верна только для некоторых специальных деревьев, включая пути [1] и деревья с радиусом два. [15]
Еще одна нерешенная проблема на -ограниченность была сформулирована Луи Эспере, который спросил, каждый ли наследственный класс графов -bounded имеет функцию которая растет не более чем полиномиально как функция . [6]
В наследственном -ограниченный класс графа, является ли хроматическое число не более полиномиальным от размера клики?
Рекомендации
- ^ a b Гьярфас, А. (1987), "Проблемы из мира, окружающего совершенные графы", Труды Международной конференции по комбинаторному анализу и его приложениям (Pokrzywna, 1985), Zastosowania Matematyki , 19 (3–4): 413– 441 (1988), Руководство по ремонту 0951359
- ^ Зыков А.А. О некоторых свойствах линейных комплексов // Матем. Сборник , Новые серии, 24 (66): 163–188, MR 0035428. Переведен на английский на амер. Математика. Soc. Перевод , 1952, MR0051516 . Как цитируется Павлик и др. (2014)
- ^ Mycielski, Ян (1955), "Sur le coloriage des graphs", Colloq. Математика. (по - французски), 3 (2): 161-162, DOI : 10.4064 / см-3-2-161-162 , МР 0069494
- ^ а б Павлик, Аркадиуш; Козик, Якуб; Кравчик, Томаш; Ласонь, Михал; Мичек, Петр; Троттер, Уильям Т .; Вальчак, Бартош (2014), «Графы пересечений без треугольников отрезков прямых с большим хроматическим числом», Журнал комбинаторной теории , серия B, 105 : 6–10, arXiv : 1209.1595 , doi : 10.1016 / j.jctb.2013.11. 001 , Руководство 3171778 , S2CID 9705484
- ^ а б Чудновский, Мария ; Seymour, Paul (2010), "лапка свободных графиков VI Раскраска.", Журнал комбинаторной теории , серии B, 100 (6): 560-572, DOI : 10.1016 / j.jctb.2010.04.005 , MR 2718677
- ^ а б Karthick, T .; Маффре, Фредерик (2016), «Граница Визинга для хроматического числа на некоторых классах графов», Графы и комбинаторика , 32 (4): 1447–1460, DOI : 10.1007 / s00373-015-1651-1 , MR 3514976 , S2CID 41279514
- ^ Asplund, E .; Грюнбаум, В. (1960), "Об одной проблеме окраски", Mathematica Scandinavica , 8 : 181-188, DOI : 10,7146 / math.scand.a-10607 , МР 0144334
- ^ Чалермсук; Вальчак (2020), Раскраска и набор прямоугольников , не зависящий от максимального веса , arXiv : 2007.07880
- ^ Дворжак, Зденек; Краль, Даниэль (2012), "Классы графов с разложениями малого ранга являются-bounded », Электронный журнал комбинаторики , 33 (4): 679–683, arXiv : 1107.2161 , doi : 10.1016 / j.ejc.2011.12.005 , MR 3350076 , S2CID 5530520
- ^ Ким, Сог-Джин; Косточка, Александр; Nakprasit, Kittikorn (2004), "О хроматического числа пересечений графов выпуклых множеств на плоскости" , Электронный журнал комбинаторике , 11 (1), R52, DOI : 10,37236 / 1805 , MR 2097318
- ^ Дэвис; Маккарти (2020), «Круговые графы квадратично ограничены по χ» , Бюллетень Лондонского математического общества , arXiv : 1905.11578v1 , doi : 10.1112 / blms.12447 , S2CID 167217723
- ^ Рок, Александр; Вальчак, Бартош (2014), «Графы внешней струны-ограниченное», Труды тридцатого ежегодного симпозиума по вычислительной геометрии (SoCG'14) , Нью - Йорк.: АКМ, С. 136-143, DOI : 10,1145 / 2582112,2582115 , MR 3382292 , S2CID 33362942
- ^ Рок; Вальчак (2019), «Графы внешних цепей являются $ \ chi $ -ограниченными» , Журнал SIAM по дискретной математике , 33 (4): 2181–2199, arXiv : 1312.1559 , doi : 10.1137 / 17M1157374 , S2CID 9474387
- ^ Рок; Вальчак (2019), "Красящие Кривые , которые пересекают фиксированную кривой" , Дискретная & Вычислительная геометрия , 61 (4): 830-851, DOI : 10.1007 / s00454-018-0031-г , S2CID 124706442
- ^ Кирстед, штат Джорджия; Пенрис, С.Г. (1994), "Радиус двух деревьев указывает-ограниченных классы», Журнал теории графов , 18 (2): 119-129, DOI : 10.1002 / jgt.3190180203 , МР 1258244
Внешние ссылки
- Хи-ограниченный , открытый проблемный сад