完美图

完美图是一个图 ，对于 的每个导出子图，其团数等于色数，即 。不是完美图的图称为不完美图（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. 风车图。