algorithm - DFS 贪心色数

Question

在我的学校里，我了解到计算任意图的色数是 NP 完全的。 我明白为什么 greddy 算法不起作用，但是 DFS/Greedy 算法呢？ 主要思想是对所有尚未着色的顶点进行 DFS，取所有邻居的最小颜色索引。

我想不出反例，这个问题让我大吃一惊。 感谢您的所有回答。

伪代码

Chromatic(Vertex x){
    for each neighbour y of vertex x
        if color(y) = -1
           color(y) <- minimum color over all the neighbours of y
           if(y>=numColor) numColors++;
           Chromatic(y);
}
Main(){
  Set the color of all vertex equal -1
  Take an arbitrary vertex u and set color(u) = 0
  numColors = 1;
  Chromatic(u);
  print numColors;
}

Answer 1

这是一个具体的反例:petersen graph 。无论你从哪里开始(我认为)，你的算法都会计算 4，但图表的色度索引是 3。

彼得森图是图问题上许多贪婪尝试以及图论猜想的经典反例。