Гранди номер

В теории графов число Гранди или хроматическое число Гранди неориентированного графа — это максимальное количество цветов, которое может использоваться жадной стратегией раскраски , которая рассматривает вершины графа последовательно и присваивает каждой вершине свой первый доступный цвет, используя порядок вершин выбран так, чтобы использовать как можно больше цветов. Числа Гранди названы в честь П.М. Гранди , который изучал аналогичную концепцию ориентированных графов в 1939 году. ^[1] Нережиссированная версия была представлена Кристеном и Селковом (1979) . ^[2]

Примеры

Граф путей с четырьмя вершинами представляет собой простейший пример графа, хроматическое число которого отличается от его числа Гранди. Этот граф можно раскрасить в два цвета, но его число Гранди равно трем: если сначала раскрасить две конечные точки пути, жадный алгоритм раскраски будет использовать три цвета для всего графа. ^[3]

Полные двудольные графы — единственные связные графы, у которых число Гранди равно двум. Все остальные связные графы содержат либо треугольник, либо путь из четырех вершин, в результате чего число Гранди становится не меньше трех. ^[3]

Графы короны получаются из полных двудольных графов. $K_{n,n}$ путем удаления идеального соответствия . В результате для каждой вершины на одной стороне биразделения существует ровно одна вершина на противоположной стороне биразделения, с которой она не является смежной. Как двудольные графы, их можно раскрасить в два цвета, но их число Гранди равно $n$ : если жадный алгоритм раскраски рассматривает каждую совпавшую пару вершин по порядку, каждая пара получит свой цвет. Как показывает этот пример, число Гранди может быть больше хроматического числа в коэффициент, линейный по числу вершин графа. ^[4]

Атомы

Закер (2006) определяет последовательность графов, называемую $t$ - атомами , со свойством, что граф имеет число Гранди не меньше $t$ тогда и только тогда, когда он содержит $t$ -атом.Каждый $t$ -атом формируется из независимого набора и $(t - 1)$ -атома путем добавления одного ребра из каждой вершины $(t - 1)$ -атома к вершине независимого набора таким образом, что каждое член независимого множества имеет хотя бы одно инцидентное ему ребро.Раскраску Гранди $t$ -атома можно получить, раскрасив независимый набор сначала в цвет с наименьшим номером, а затем раскрасив оставшийся $(t - 1)$ -атом в дополнительные $t - 1$ цвета.Например, единственный 1-атом — это одна вершина, а единственный 2-атом — это одно ребро, но существует два возможных 3-атома: треугольник и путь из четырех вершин. ^[3]

В разреженных графах

Для графа с $n$ вершинами и вырожденностью $d$ число Гранди равно $O (d log n)$ . В частности, для графов ограниченного вырождения (таких как плоские графы ) или графов, для которых хроматическое число и вырождение ограничены в пределах постоянных множителей друг друга (таких как хордальные графы ), число Гранди и хроматическое число находятся в пределах логарифмического множителя каждого другой. ^[5] Для интервальных графиков хроматическое число и число Гранди отличаются друг от друга в пределах 8 раз. ^[6]

Вычислительная сложность

Проверка того, составляет ли число Гранди данного графа по крайней мере $k$ для фиксированной константы $k$ , может быть выполнена за полиномиальное время путем поиска всех возможных $k$ -атомов, которые могут быть подграфами данного графа. Однако этот алгоритм не является управляемым с фиксированными параметрами , поскольку показатель степени во время его работы зависит от $k$ . Когда $k$ является входной переменной, а не параметром, проблема является NP-полной . ^[3] Число Гранди равно не более единице плюс максимальная степень графа, и оно остается NP-полным, чтобы проверить, равно ли оно единице плюс максимальная степень. ^[7] Существует константа $c > 1$ , такая что NP-трудно при рандомизированных сокращениях аппроксимировать число Гранди с точностью до коэффициента аппроксимации, лучшего, чем $c$ . ^[8]

Существует точный алгоритм экспоненциального времени для числа Гранди, который работает за время $O (2,443 н)$ . ^[9]

Для деревьев и графов ограниченной ширины дерева число Гранди может быть неограниченно большим. ^[10] Тем не менее, число Гранди можно вычислить за полиномиальное время для деревьев:и является управляемым с фиксированными параметрами, если параметризован как шириной дерева , так и числом Гранди, ^[11] хотя (при условии гипотезы экспоненциального времени ) зависимость от ширины дерева должна быть больше, чем однократно экспоненциальная. ^[9] При параметризации только числом Гранди его можно вычислить за приемлемое время с фиксированным параметром для хордальных графов и графов без когтей . ^[9] а также (с использованием общих результатов об изоморфизме подграфов в разреженных графах для поиска атомов) для графов ограниченного расширения . ^[9]^[12]^[13]Однако на общих графах проблема W[1]-сложна, если она параметризована числом Гранди. ^[14]

Красочные графики

Граф называется хорошо раскрашенным, если его число Гранди равно хроматическому числу. Проверка того, хорошо ли раскрашен граф, является coNP-полной. ^[3] Наследственно индуцированный хорошо окрашенные графы (графы, для которых каждый подграф хорошо окрашен) — это в точности кографы , графы, которые не имеют пути с четырьмя вершинами в качестве индуцированного подграфа. ^[2]

Ссылки

^ Гранди, ПМ (1939), «Математика и игры» , Эврика , 2 : 6–8, заархивировано из оригинала 27 сентября 2007 г. Как цитирует Эрдеш, Пол ; Хедетниеми, Стивен Т.; Ласкар, Рену К .; Принс, Герт CE (2003), «О равенстве частичных чисел Гранди и верхних охроматических чисел графов», Discrete Mathematics , 272 (1): 53–64, doi : 10.1016/S0012-365X(03)00184-5 , МР 2019200 .
^ Jump up to: Перейти обратно: ^а ^б Кристен, Клод А.; Селков, Стэнли М. (1979), «Некоторые идеальные свойства раскраски графов», Журнал комбинаторной теории , серия B, 27 (1): 49–59, doi : 10.1016/0095-8956(79)90067-4 , MR 0539075 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Закер, Манучехр (2006), «Результаты по хроматическому числу графов Гранди», Discrete Mathematics , 306 (23): 3166–3173, doi : 10.1016/j.disc.2005.06.044 , MR 2273147 .
^ Джонсон, Д.С. (1974), "Поведение алгоритмов раскраски графов в наихудшем случае", Proc. 5-я Юго-Восточная конф. по комбинаторике, теории графов и информатике, Utilitas Mathematicae , Виннипег, стр. 513–527, MR 0389644. {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Ирани, Сэнди (1994), «Раскраска индуктивных графов в режиме онлайн», Algorithmica , 11 (1): 53–72, doi : 10.1007/BF01294263 , MR 1247988 , S2CID 181800 .
^ Нараянасвами, Н.С.; Субхаш Бабу, Р. (2008), «Заметки о раскраске интервальных графов по первому требованию», Order , 25 (1): 49–53, doi : 10.1007/s11083-008-9076-6 , MR 2395157 , S2CID 207223738 .
^ Хаве, Фредерик; Сампайо, Леонардо (2010), «О числе Гранди графа», Параметризованные и точные вычисления , Конспекты лекций по вычислениям. наук, том. 6478, Springer, Berlin, стр. 170–179, Bibcode : 2010LNCS.6478..170H , doi : 10.1007/978-3-642-17493-3_17 , ISBN 978-3-642-17492-6 , МР 2770795 .
^ Корцарц, Гай (2007), «Нижняя граница аппроксимации нумерации Гранди» , Дискретная математика и теоретическая информатика , 9 (1) .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Бонне, Эдуард; Фуко, Флоран; Ким, Ын Чжон ; Сикора, Флориан (2015), «Сложность раскраски Гранди и ее вариантов», Вычисления и комбинаторика , Конспекты лекций по вычислениям. наук, том. 9198, Спрингер, Чам, стр. 109–120, arXiv : 1407.5336 , doi : 10.1007/978-3-319-21398-9_9 , ISBN 978-3-319-21397-2 , МР 3447246 , S2CID 5514223 .
^ Дьярфас, А.; Лехель, Дж. (1988), «Онлайн-раскраски графов и раскраски по первому требованию», Journal of Graph Theory , 12 (2): 217–227, doi : 10.1002/jgt.3190120212 , MR 0940831 , S2CID 8839035 .
^ Телле, Ян Арне; Проскуровски, Анджей (1997), «Алгоритмы для задач разделения вершин на частичных $k-$ деревьях», SIAM Journal on Discrete Mathematics , 10 (4): 529–550, CiteSeerX 10.1.1.25.152 , doi : 10.1137/S0895480194275825 , MR 1477 655 .
^ Дворжак, Зденек ; Краль, Даниэль ; Томас, Робин (2010), «Определение свойств первого порядка для разреженных графов», Proc. 51-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS 2010) , IEEE Computer Soc., Лос-Аламитос, Калифорния, стр. 133–142, MR 3024787 .
^ Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «18.3 Проблема изоморфизма подграфов и логические запросы», Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Springer, стр. 400–401, номер документа : 10.1007/978-3-642-27875-4 , ISBN. 978-3-642-27874-7 , МР 2920058 .
^ Абулкер, Пьер; Бонне, Эдуард; Ким, Ын Юнг; Сикора, Флориан (2023), «Раскраска Гранди и друзья, полуграфы, биклики», Algorithmica , 85 : 1–28, doi : 10.1007/s00453-022-01001-2 , S2CID 250614665 .

[1] Гранди, ПМ (1939), «Математика и игры» , Эврика , 2 : 6–8, заархивировано из оригинала 27 сентября 2007 г. Как цитирует Эрдеш, Пол ; Хедетниеми, Стивен Т.; Ласкар, Рену К .; Принс, Герт CE (2003), «О равенстве частичных чисел Гранди и верхних охроматических чисел графов», Discrete Mathematics , 272 (1): 53–64, doi : 10.1016/S0012-365X(03)00184-5 , МР 2019200 .

[cs79-2] Jump up to: Перейти обратно: ^а ^б Кристен, Клод А.; Селков, Стэнли М. (1979), «Некоторые идеальные свойства раскраски графов», Журнал комбинаторной теории , серия B, 27 (1): 49–59, doi : 10.1016/0095-8956(79)90067-4 , MR 0539075 .

[z-3] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Закер, Манучехр (2006), «Результаты по хроматическому числу графов Гранди», Discrete Mathematics , 306 (23): 3166–3173, doi : 10.1016/j.disc.2005.06.044 , MR 2273147 .

[4] Джонсон, Д.С. (1974), "Поведение алгоритмов раскраски графов в наихудшем случае", Proc. 5-я Юго-Восточная конф. по комбинаторике, теории графов и информатике, Utilitas Mathematicae , Виннипег, стр. 513–527, MR 0389644. {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[5] Ирани, Сэнди (1994), «Раскраска индуктивных графов в режиме онлайн», Algorithmica , 11 (1): 53–72, doi : 10.1007/BF01294263 , MR 1247988 , S2CID 181800 .

[6] Нараянасвами, Н.С.; Субхаш Бабу, Р. (2008), «Заметки о раскраске интервальных графов по первому требованию», Order , 25 (1): 49–53, doi : 10.1007/s11083-008-9076-6 , MR 2395157 , S2CID 207223738 .

[7] Хаве, Фредерик; Сампайо, Леонардо (2010), «О числе Гранди графа», Параметризованные и точные вычисления , Конспекты лекций по вычислениям. наук, том. 6478, Springer, Berlin, стр. 170–179, Bibcode : 2010LNCS.6478..170H , doi : 10.1007/978-3-642-17493-3_17 , ISBN 978-3-642-17492-6 , МР 2770795 .

[8] Корцарц, Гай (2007), «Нижняя граница аппроксимации нумерации Гранди» , Дискретная математика и теоретическая информатика , 9 (1) .

[bfks-9] Jump up to: Перейти обратно: ^а ^б ^с ^д Бонне, Эдуард; Фуко, Флоран; Ким, Ын Чжон ; Сикора, Флориан (2015), «Сложность раскраски Гранди и ее вариантов», Вычисления и комбинаторика , Конспекты лекций по вычислениям. наук, том. 9198, Спрингер, Чам, стр. 109–120, arXiv : 1407.5336 , doi : 10.1007/978-3-319-21398-9_9 , ISBN 978-3-319-21397-2 , МР 3447246 , S2CID 5514223 .

[10] Дьярфас, А.; Лехель, Дж. (1988), «Онлайн-раскраски графов и раскраски по первому требованию», Journal of Graph Theory , 12 (2): 217–227, doi : 10.1002/jgt.3190120212 , MR 0940831 , S2CID 8839035 .

[11] Телле, Ян Арне; Проскуровски, Анджей (1997), «Алгоритмы для задач разделения вершин на частичных $k-$ деревьях», SIAM Journal on Discrete Mathematics , 10 (4): 529–550, CiteSeerX 10.1.1.25.152 , doi : 10.1137/S0895480194275825 , MR 1477 655 .

[12] Дворжак, Зденек ; Краль, Даниэль ; Томас, Робин (2010), «Определение свойств первого порядка для разреженных графов», Proc. 51-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS 2010) , IEEE Computer Soc., Лос-Аламитос, Калифорния, стр. 133–142, MR 3024787 .

[13] Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «18.3 Проблема изоморфизма подграфов и логические запросы», Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Springer, стр. 400–401, номер документа : 10.1007/978-3-642-27875-4 , ISBN. 978-3-642-27874-7 , МР 2920058 .

[14] Абулкер, Пьер; Бонне, Эдуард; Ким, Ын Юнг; Сикора, Флориан (2023), «Раскраска Гранди и друзья, полуграфы, биклики», Algorithmica , 85 : 1–28, doi : 10.1007/s00453-022-01001-2 , S2CID 250614665 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]