algorithm - 求这个修改区间图的色数问题是NP-Complete吗？

Question

几天前，我正在研究区间图来解决已知的资源分配问题，因为我们知道有一种贪婪的方法可以在多项式时间内解决这个问题(色数)并为我们提供每个顶点的颜色区间图(求一般图中色数的问题是NP-Complete(3-satisfiability reduction by Karp))。

我想知道:如果有一个图不是区间图，但这是因为它有一个且只有一个长度 > 3 的无弦循环(有一条边，当你删除它时，图变成一个区间graph), 是否使得在这种图上求色数的问题成为NP-Complete？

Answer 1

有点手忙脚乱，如果只有一条边阻止区间图着色算法工作，则将其删除。运行区间图算法。如果移除边的两个端点有不同的颜色，你就完成了。否则，令 C 为算法使用的颜色数。为两个端点尝试所有(C选择2)固定颜色，并再次尝试区间图算法。如果它使用 C 颜色成功，那么您就完成了。否则，您将需要 C+1 种颜色，因此只需选择一个端点并为其指定一种独特的颜色。

我假设您可以在多边形时间内找到可移动边。