線完美圖

在圖論中，線完美圖(line perfect graph)是其線圖為完美圖的圖。同樣的，這些圖中每個奇數長度的簡單環都是一個三角形。^[1]

若且唯若一個圖的任意雙連接組件都是二分圖、完全圖 $K_{4}$ 或三角形書 $K_{1,1,n}$ 時，該圖被稱為線完美的，^[2]因為這三種類型的雙連接組件本身是完美圖，其形成的線圖本身是完美的。^[1] 通過類似的推理，所有的線完美圖都是奇偶圖^[3]、梅尼爾圖^[4]和完全有序圖.

線完美圖推廣了二部圖，並與二部圖共同擁有最大匹配和最小頂點覆蓋有相同尺寸以及色指數等於最大度的性質。^[5]

參見編輯

^ ^1.0 ^1.1 Trotter, L. E., Jr., Line perfect graphs, Mathematical Programming, 1977, 12 (2): 255–259, MR 0457293, doi:10.1007/BF01593791
^ Maffray, Frédéric, Kernels in perfect line-graphs, 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, Geometric algorithms and combinatorial optimization, 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, Critical and anticritical edges in perfect graphs, Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001, Proceedings, Lecture Notes in Computer Science 2204, Berlin: Springer: 317–327, 2001, MR 1905643, doi:10.1007/3-540-45477-2_29 .
^ de Werra, D., On line-perfect graphs, Mathematical Programming, 1978, 15 (2): 236–238, MR 0509968, doi:10.1007/BF01609025 .