主題
Search

強完美圖


如果圖的每個匯出子圖 H 都存在一個獨立頂點集,該集合與 H 的所有極大團相交,則該圖是強完美圖(Berge 和 Duchet 1984, Ravindra 1999)。

每個強完美圖都是完美圖,但反之不一定成立。

每個 P_4-無圖(即,每個不包含路徑圖 路徑圖 P_4 作為頂點匯出子圖的圖)都是強完美圖 (Ravindra 1999)。


另請參閱

完美圖, 弱完美圖

使用 探索

參考文獻

Berge, C. and Duchet, P. "Strongly Perfect Graphs." Ann. Disc. Math. 21, 57-61, 1984.Ravindra, G. "Some Classes of Strongly Perfect Graphs." Disc. Math. 206, 197-203, 1999.Wang, H. Y. "Which Claw-Free Graphs Are Strongly Perfect?" Disc. Math. 306, 2602-2629, 2006.

請引用為

韋斯坦, 埃裡克·W. "強完美圖。" 來自 Web 資源。 https://mathworld.tw/StronglyPerfectGraph.html

主題分類