Является ли проблема нахождения хроматического числа этого модифицированного интервального графа NP-полной?

Question

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

Мне было интересно: если бы имелся граф, который не является интервальным графом, но это потому, что он имеет один и только один аккордовый цикл длины> 3 (есть ребро, которое, когда вы удаляете его, граф становится интервалом график), делает ли это проблему нахождения хроматического числа на этом типе графа NP-Complete?

Answer 1

Отчасти волнистый, если есть только одно ребро, которое препятствует работе алгоритма раскраски интервального графа, то удалите его.Запустите алгоритм интервального графа.Если две конечные точки удаленного края имеют разные цвета, все готово.В противном случае, пусть C будет количеством цветов, которые использовал алгоритм.Попробуйте все (C выберите 2) фиксированные цвета для двух конечных точек и попробуйте алгоритм графа интервала снова.Если это удастся с цветами C, все готово.В противном случае вам потребуются цвета C + 1, поэтому просто выберите одну из конечных точек и присвойте ей уникальный цвет.

Я предполагаю, что вы можете найти съемный край за время поли.