线完美图
在图论中,线完美图(line perfect graph)是其线图为完美图的图。同样的,这些图中每个奇数长度的简单环都是一个三角形。[1]
当且仅当一个图的任意双连接组件都是二分图、完全图或三角形书 时,该图被称为线完美的,[2]因为这三种类型的双连接组件本身是完美图,其形成的线图本身是完美的。[1] 通过类似的推理,所有的线完美图都是奇偶图[3]、梅尼尔图[4]和完全有序图.
参见
- 绞合图,每一个外环都是三角形的图
参考文献
- Trotter, L. E., Jr., , Mathematical Programming, 1977, 12 (2): 255–259, MR 0457293, doi:10.1007/BF01593791
- Maffray, Frédéric, , Journal of Combinatorial Theory, Series B, 1992, 55 (1): 1–8, MR 1159851, doi:10.1016/0095-8956(92)90028-V.
- Grötschel, Martin; Lovász, László; Schrijver, Alexander, , Algorithms and Combinatorics 2 2nd, Springer-Verlag, Berlin: 281, 1993, ISBN 3-540-56740-2, MR 1261419, doi:10.1007/978-3-642-78240-4.
- Wagler, Annegret, , , Lecture Notes in Computer Science 2204, Berlin: Springer: 317–327, 2001, MR 1905643, doi:10.1007/3-540-45477-2_29.
- de Werra, D., , Mathematical Programming, 1978, 15 (2): 236–238, MR 509968, doi:10.1007/BF01609025.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.