Perfect Graph

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)一次規劃演算法。目前還沒有純粹的圖論解法。

Perfectly Ordered Graph

可以用Greedy Method進行點著色的圖。時間複雜度O(V+E)。

弦圖本身也有線性時間演算法可以求出  最小點著色/最小圖覆蓋/最大團/最大獨立集
首先找出一個 PEO
[Maffray 2003] 弦圖的任何一個PEO顛倒過來  用greedy method著色  必定得到最小點著色

Skew Partition

http://en.wikipedia.org/wiki/Skew_partition