主題
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.tw/StrongPerfectGraphTheorem.html

主題分類