Хорошо цветной график

В теории графов , подразделе математики, хорошо раскрашенный граф — это неориентированный граф, для которого при жадной раскраске используется одинаковое количество цветов независимо от порядка, в котором цвета выбраны для его вершин. То есть для этих графов хроматическое число (минимальное количество цветов) и число Гранди (максимальное количество жадно выбранных цветов) равны. ^[1]

Примеры

К хорошо раскрашенным графам относятся полные графы нечетной длины и графы циклов (графы, которые образуют исключительные случаи теоремы Брукса ), а также полные двудольные графы и полные многодольные графы .

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

Сложность

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

Связанные свойства

Граф наследственно хорошо окрашен, если каждый индуцированный подграф хорошо окрашен. Наследственно хорошо раскрашенные графы — это в точности кографы , графы, у которых нет пути с четырьмя вершинами в качестве индуцированного подграфа. ^[4]

Ссылки

^ Перейти обратно: ^а ^б Закер, Манучехр (2006), «Результаты по хроматическому числу графов Гранди», Discrete Mathematics , 306 (23): 3166–3173, doi : 10.1016/j.disc.2005.06.044 , MR 2273147
^ Хансен, Пьер; Куплинский, Хулио (1991), «Самый маленький граф, который трудно раскрасить», Discrete Mathematics , 96 (3): 199–212, doi : 10.1016/0012-365X(91)90313-Q , MR 1139447
^ Косовский, Адриан; Манушевский, Кшиштоф (2004), «Классическая раскраска графов», Раскраски графов , Современная математика, том. 352, Провиденс, Род-Айленд: Американское математическое общество, стр. 1–19, doi : 10.1090/conm/352/06369 , ISBN. 978-0-8218-3458-9 , МР 2076987
^ Кристен, Клод А.; Селков, Стэнли М. (1979), «Некоторые идеальные свойства раскраски графов», Журнал комбинаторной теории , серия B, 27 (1): 49–59, doi : 10.1016/0095-8956(79)90067-4 , MR 0539075

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

[hk-2] Хансен, Пьер; Куплинский, Хулио (1991), «Самый маленький граф, который трудно раскрасить», Discrete Mathematics , 96 (3): 199–212, doi : 10.1016/0012-365X(91)90313-Q , MR 1139447

[km-3] Косовский, Адриан; Манушевский, Кшиштоф (2004), «Классическая раскраска графов», Раскраски графов , Современная математика, том. 352, Провиденс, Род-Айленд: Американское математическое общество, стр. 1–19, doi : 10.1090/conm/352/06369 , ISBN. 978-0-8218-3458-9 , МР 2076987

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

[1]

[2]

[3]

[4]