主题
Search

强完美图定理

该定理最初由 Berge (1960, 1961) 猜想，即一个图是 完美图 当且仅当 该图及其图补图 都不包含长度至少为五的奇数图环 作为导出子图，后来被称为强完美图猜想 (Golumbic 1980; Skiena 1990, p. 221)。该猜想可以更简单地表述为一个图是完美图 当且仅当 它不包含奇数图洞 且不包含奇数图反洞。这个命题甚至可以更简洁地表述为“一个图是完美图 当且仅当 它是一个贝尔热图。”

该猜想在 2002 年 5 月被证明，此前 Chudnovsky、Robertson、Seymour 和 Thomas 取得了一系列卓越的成果 (Cornuéjols 2002, MacKenzie 2002)。

另请参阅

贝尔热图, 大胆猜想, 无弦环, 图反洞, 图洞, 完美图, 完美图定理

使用 探索

参考文献

Berge, C. "Les problèmes de coloration en théorie des graphes." Publ. Inst. Stat. Univ. Paris 9, 123-160, 1960.Berge, C. "Färbung von Graphen deren sämtliche beziehungsweise deren ungerade Kreise starr sind (Zusammenfassung)." Wissenschaftliche Zeitschrift, Martin Luther Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe, 114-115, 1961.Berge, C. 和 Ramírez-Alfonsiin, J. L. "Origins and Genesis." In Perfect Graphs (Ed. J. L. Ramírez-Alfonsín 和 B. A. Reed)。纽约：Wiley，pp. 1-12, 2001。Chvátal, V. "The Strong Perfect Graph Theorem." http://www.cs.concordia.ca/~chvatal/perfect/spgt.html.Cornuéjols, G. "The Strong Perfect Graph Conjecture." International Congress of Mathematics, Beijing, China, 2002, Vol. 3. pp. 547-559. http://integer.gsia.cmu.edu/webpub/SPGCsurvey.pdf.Fonlupt, J. 和 Sebő, A. "On the Clique-Rank and the Coloration of Prefect Graphs." In Integer Programming and Combinatorial Optimization, Vol. 1 (Ed. R. Kannan 和 W. R. Pulleyblank)。滑铁卢，安大略省：University of Waterloo，pp. 201-216, 1990。Golumbic, M. C. Algorithmic Graph Theory and Perfect Graphs. 纽约：Academic Press，1980。Jensen, T. R. 和 Toft, B. Graph Coloring Problems. 纽约：Wiley，1995。MacKenzie, D. "Graph Theory Uncovers the Roots of Perfection." Science 297, 38, 2002.Sebő, A. "On Critical Edges in Minimal Perfect Graphs." J. Combin. Th. B 67, 62-85, 1996.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. 雷丁，马萨诸塞州：Addison-Wesley，1990。West, D. B. "The Strong Perfect Graph Conjecture." Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ：Prentice-Hall，pp. 341-344, 2000。

在 中被引用

强完美图定理

请引用为

Weisstein, Eric W. “强完美图定理。” 来自 —— 资源。https://mathworld.net.cn/StrongPerfectGraphTheorem.html

主题分类