完美圖

完美圖是一個圖 ，對於 的每個匯出子圖，其團數等於色數，即 。不是完美圖的圖稱為不完美圖（Godsil 和 Royle 2001, p. 142）。

對於滿足 的圖（沒有要求此條件也適用於匯出子圖），稱為弱完美圖。因此，根據定義，所有完美圖都是弱完美圖。

如果每個匯出子圖 都有一個獨立集，與 的所有極大團相交，則該圖是強完美圖。雖然所有強完美圖都是完美圖，但反之不一定成立。由於每個無 圖（其中 是一個路徑圖）是強完美的 (Ravindra 1999)，並且每個強完美圖都是完美的，因此如果一個圖是無 圖，則它是完美的。

Berge (1973) 引入完美圖，部分原因是受確定圖的夏農容量的啟發 (Bohman 2003)。請注意，非常容易混淆的是，完美圖與具有完美匹配的圖類不同。

每個二分圖都是完美的（Gross 和 Yellen 2006, p. 385）。完美圖定理指出，完美圖的補圖本身也是完美的。因此，一個圖是完美的當且僅當其補圖是完美的。然而，已證明確定一般圖是否是完美圖是多項式時間演算法（Chudnovsky et al. 2005）。

一個圖是完美的當且僅當圖 及其補圖 都沒有奇無弦環。因此，沒有 5 環且沒有更大的奇無弦環的圖自動是完美的。這是正確的，因為 中存在無弦 5 環對應於 中的 5 環，並且 不能有無弦 7 環或更大的環，因為 中這些環的對角線將在 中包含一個 5 環。

可以使用以下方法測試圖是否是完美的：PerfectQ[g] 在 Wolfram 語言 包中Combinatorica` .

節點數為 , 2, ... 的完美圖的數量為 1, 2, 4, 11, 33, 148, 906, 8887, ... (OEIS A052431)。

節點數為 , 2, ... 的完美連通圖的數量為 1, 1, 2, 6, 20, 105, 724, ... (OEIS A052433)。

完美圖的類別包括：

1. 二分圖，

2. 塊圖，

3. 弦圖，

4. 距離遺傳圖，

5. 線圖 的 二分圖，

6. Meyniel 圖，

7. 樹，

8. 補圖 的 二分圖，以及

9. 補圖 的 線圖 的 二分圖。

完美圖的族（不包括二分族）包括：

1. 啞鈴圖，

2. 象圖，

3. 穴居人圖，

4. 完全圖 ，

5. - 雙錐圖，對於 或 偶數，

6. 空圖 ，

7. 扇圖，

8. 河內圖，

9. 舵圖 ，對於 或 偶數，

10. 車圖，

11. 棒棒糖圖，

12. 王圖 ，其中 ，

13. 托勒密圖，

14. 後圖 、 和 ，

15. 太陽圖，

16. 圖蘭圖，

17. 三角形蛇圖 ，以及

18. 風車圖。