求这个修正区间图的色数问题是NP完全问题吗？
几天前，我正在研究区间图来解决已知的资源分配问题，因为我们知道有一种贪心方法可以在多项式时间内解决这个问题（色数），并为我们提供区间图中每个顶点的颜色（在一般图中求色数的问题是 NP 完全问题（Karp 的 3-可满足性约简）。
我想知道：是否有一个图不是区间图，但它是因为它有一个且只有一个无弦循环长度> 1。 3（有一条边，当你删除它时，图就变成了区间图），这是否使得在这种图上求色数的问题成为NP完全问题？
Few days ago I was working on interval graphs to solve the known problem of resource allocation, as we know there is a greedy approach that solves this problem (chromatic number) in polynomial time and gives us the colors of each vertex in the interval graph (the problem of finding the chromatic number in general graphs is NP-Complete (3-satisfiability reduction by Karp)).
I was wondering: if had a graph that is not an interval graph but it is because it has one and only one chordless cycle of length > 3 (there is an edge that, when you remove it, the graph becomes an interval graph), does it makes the problem of finding the chromatic number on this kind of graph NP-Complete?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
有点手动，如果只有一条边阻止区间图着色算法工作，那么将其删除。运行区间图算法。如果删除的边的两个端点具有不同的颜色，则完成。否则，令 C 为算法使用的颜色数量。尝试两个端点的所有（C 选择 2）固定颜色，然后再次尝试区间图算法。如果 C 颜色成功，那么您就完成了。否则，您将需要 C+1 种颜色，因此只需选择一个端点并为其赋予唯一的颜色即可。
我假设你可以在复数时间内找到可移动的边缘。
Kind of hand-wavey, if there's just a single edge which prevents the interval graph coloring algorithm from working, then remove it. Run the interval graph algorithm. If the two endpoints of the removed edge have different colors, you're done. Otherwise, Let C be the number of colors that the algorithm used. Try all (C choose 2) fixed colors for the two endpoints, and try the interval graph algorithm again. If it succeeds with C colors, you're done. Otherwise, you'll need C+1 colors so just pick one of the endpoints and give it a unique color.
I'm assuming you can find the removable edge in poly time.