perfect graph

森林（無環）、有向無環圖（無環），二分圖（無奇環），弦圖（無洞），完美圖（無奇洞）。這一路上的變化，就是越來越多環。

【註：方便起見，洞必須長度大於3。】

每一個導出子圖，最小著色數皆等於最大團點數，就是完美圖。(1961)
原圖和補圖要嘛同時是完美圖，要嘛同時不是完美圖。(1972)
原圖暨補圖都不含長度大於3的奇洞，就是完美圖。(2002)

完美圖的補圖是完美圖。完美圖隨意刪去一些點（以及所有鄰邊），仍是完美圖，具有遞歸的性質。

perfect graph recognition

判斷一張圖是否是完美圖，時間複雜度O(V⁸)。這是2020年的結果，尚在進化當中！

《Three-in-a-Tree in Near Linear Time》

是否包含奇洞O(V⁸)。尋找最短奇洞O(V¹⁴)。

《Detecting an Odd Hole》

是否包含偶洞O(V⁹)。尋找最短偶洞O(V³¹)。

《Finding a Shortest Even Hole in Polynomial Time》

minimum vextex coloring in perfect graph

原圖的vertex coloring、補圖的clique cover，一一對應。

原圖的clique、補圖的independent set，一一對應。

（順帶一提independent set和vertex cover互補。）

一般圖的情況下，上述兩組東西沒有直接關聯。完美圖的情況下，這兩組東西被綁在一起了──但是只有極值而已：

  |minimum vertex coloring in G| = |minimum clique cover in G|
= |maximum clique in G| = |maximum independent set in G|

我只知道極值是相等的，但是不知道是如何相互對應的。

要求出這四個東西，有著O(V+E)一次規劃演算法。目前還沒有純粹的圖論解法。

skew partition

perfectly ordered graph

可以用greedy method求出最小點著色的圖，而且每個導出子圖都是最小點著色。時間複雜度O(V+E)。

順帶一提，弦圖本身也有O(V+E)演算法，可以求出最小點著色、最小圖覆蓋、最大團、最大獨立集。

弦圖的任何一個PEO顛倒過來，用greedy method著色，必定得到最小點著色。[Maffray 2003]