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

skew partition

perfectly ordered graph

perfectly ordered graph

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

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

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

distance-hereditary graph

distance-hereditary graph

cograph

ICPC 3666 7462

ptolemaic graph