DFS貪婪色數

Question

在我的學校，我瞭解到計算任意圖的色數是NP-Complete。 我明白爲什麼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

答案是，有時你必須擁有可用2種顏色頂點，而做出錯誤的選擇後會導致問題的時間未定。

假設你有頂點1到9。然後添加邊以使以下爲真。

1，2，3形成一個三角形。 3連接到4. 4，5，6做成三角形。 5，6，7做成三角形。 6，7，8做成三角形。 7,8,9做一個三角形。 8，9，1做一個三角形。 9，1，2做一個三角形。

這種顏色很容易用3種顏色進行着色。但是深度優先的貪婪算法有2種顏色可以選擇給頂點4.做出錯誤的選擇，你將需要4種顏色，而不是3種。

Answer 2

下面是一個具體的反例：petersen graph。你的算法計算4，不管你從哪裏開始（我認爲），但圖的色數爲3

Petersen圖是在圖問題很多貪婪的嘗試經典的反例，也是圖論中的猜想。