跳至內容

線完美圖

維基百科，自由的百科全書
線完美圖。針對所有雙連接組件中的邊，組件為二部分的標為黑色；組件為四面體標為藍色；組件為三角形書標為紅色。

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

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

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

參見

[編輯]

參考文獻

[編輯]
  1. ^ 1.0 1.1 Trotter, L. E., Jr., Line perfect graphs, Mathematical Programming, 1977, 12 (2): 255–259, MR 0457293, doi:10.1007/BF01593791 
  2. ^ 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 .
  3. ^ 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 .
  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 .
  5. ^ de Werra, D., On line-perfect graphs, Mathematical Programming, 1978, 15 (2): 236–238, MR 0509968, doi:10.1007/BF01609025 .
取自「https://zh.wikipedia.org/w/index.php?title=线完美图&oldid=54587202」