1

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

我想知道：如果有一个图不是区间图，而是因为它有一个且只有一个长度 > 3 的无弦循环（有一条边，当你删除它时，图变成了区间图），它是否会导致在这种图 NP-Complete 上找到色数的问题？

4

1 回答 1

0

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

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

于 2011-01-23T00:05:09.290 回答