在图论中，线完美图(line perfect graph)是其线图为完美图的图。同样的，这些图中每个奇数长度的简单环都是一个三角形。
当且仅当一个图的任意双连接组件都是二分图、完全图K_4或三角形书 K_{1,1,n}时，该图被称为线完美的，因为这三种类型的双连接组件本身是完美图，其形成的线图本身是完美的。 通过类似的推理，所有的线完美图都是奇偶图、梅尼尔图和完全有序图.
线完美图推广了二部图，并与二部图共同拥有最大匹配和最小顶点覆盖有相同尺寸以及色指数等于最大度的性质。
参见
- 绞合图，每一个外环都是三角形的图
参考文献
评论 (0)