查看“︁线完美图”︁的源代码

[[File:Line_perfect_graph.svg|缩略图|线完美图。针对所有双连接组件中的边，组件为二部分的标为黑色；组件为四面体标为蓝色；组件为三角形书标为红色。]]
在[[图论]]中，'''线完美图(line perfect graph)'''是其[[线图]]为[[完美图]]的图。同样的，这些图中每个奇数长度的[[環 (圖論)|简单环]]都是一个三角形。{{r|trotter}}

当且仅当一个图的任意[[Biconnected component|双连接组件]]都是[[二分图]]、[[完全圖|完全图]]<math>K_4</math>或[[书 (图论)|三角形书]] <math>K_{1,1,n}</math>时，该图被称为线完美的，{{r|maffray}}因为这三种类型的双连接组件本身是完美图，其形成的线图本身是完美的。{{r|trotter}} 通过类似的推理，所有的线完美图都是[[Parity graph|奇偶图]]{{r|gls}}、[[Meyniel graph|梅尼尔图]]{{r|wagler}}和[[Perfectly orderable graph|完全有序图]].

线完美图推广了二部图，并与二部图共同拥有[[匹配 (图论)|最大匹配]]和[[最小顶点覆盖]]有相同尺寸以及[[色数|色指数]]等于[[度 (图论)|最大度]]的性质。{{r|dewerra}}

== 参见 ==

* [[绞合图]]，每一个[[外环]]都是三角形的图

== 参考文献 ==
{{Reflist|refs=<ref name=dewerra>{{citation
 | last = de Werra | first = D.
 | doi = 10.1007/BF01609025
 | issue = 2
 | journal = [[Mathematical Programming]]
 | mr = 509968
 | pages = 236–238
 | title = On line-perfect graphs
 | volume = 15
 | year = 1978}}.</ref>

<ref name=gls>{{citation
 | last1 = Grötschel | first1 = Martin | author1-link = Martin Grötschel
 | last2 = Lovász | first2 = László | author2-link = László Lovász
 | last3 = Schrijver | first3 = Alexander | author3-link = Alexander Schrijver
 | doi = 10.1007/978-3-642-78240-4
 | edition = 2nd
 | isbn = 3-540-56740-2
 | mr = 1261419
 | page = 281
 | publisher = Springer-Verlag, Berlin
 | series = Algorithms and Combinatorics
 | title = Geometric algorithms and combinatorial optimization
 | url = https://books.google.com/books?id=hWvmCAAAQBAJ&pg=PA281
 | volume = 2
 | year = 1993}}.</ref>

<ref name=maffray>{{citation
 | last = Maffray | first = Frédéric
 | doi = 10.1016/0095-8956(92)90028-V
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 1159851
 | pages = 1–8
 | series = Series B
 | title = Kernels in perfect line-graphs
 | volume = 55
 | year = 1992}}.</ref>

<ref name=trotter>{{citation
 | last = Trotter | first = L. E., Jr.
 | doi = 10.1007/BF01593791
 | issue = 2
 | journal = [[Mathematical Programming]]
 | mr = 0457293
 | pages = 255–259
 | title = Line perfect graphs
 | volume = 12
 | year = 1977}}</ref>

<ref name=wagler>{{citation
 | last = Wagler | first = Annegret
 | contribution = Critical and anticritical edges in perfect graphs
 | doi = 10.1007/3-540-45477-2_29
 | mr = 1905643
 | pages = 317–327
 | publisher = Springer | location = Berlin
 | series = Lecture Notes in Computer Science
 | title = Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001, Proceedings
 | volume = 2204
 | year = 2001}}.</ref>}}
[[Category:图论]]
[[Category:有未审阅翻译的页面]]