Strong Perfect Graph Theorem

The theorem, originally conjectured by Berge (1960, 1961), that a graph is perfect iff neither the graph nor its graph complement contains an odd graph cycle of length at least five as an induced subgraph became known as the strong perfect graph conjecture (Golumbic 1980; Skiena 1990, p. 221). The conjecture can be stated more simply as the assertion that a graph is perfect iff it contains no odd graph hole and no odd graph antihole. The proposition can be stated even more succinctly as "a graph is perfect iff it is a Berge graph."

This conjecture was proved in May 2002 following a remarkable sequence of results by Chudnovsky, Robertson, Seymour, and Thomas (Cornuéjols 2002, MacKenzie 2002).

---

REFERENCES

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. and Ramírez-Alfonsiin, J. L. "Origins and Genesis." In Perfect Graphs (Ed. J. L. Ramírez-Alfonsín and B. A. Reed). New York: 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. and Sebő, A. "On the Clique-Rank and the Coloration of Prefect Graphs." In Integer Programming and Combinatorial Optimization, Vol. 1 (Ed. R. Kannan and W. R. Pulleyblank). Waterloo, Ontario: University of Waterloo, pp. 201-216, 1990.

Golumbic, M. C. Algorithmic Graph Theory and Perfect Graphs. New York: Academic Press, 1980.

Jensen, T. R. and Toft, B. Graph Coloring Problems. New York: 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. Reading, MA: 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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

متحف الكفيل يباشر صيانة المجموعة الرابعة من مقتنيات العتبة العسكرية المقدسة

ضمن برنامجها التبليغي اليومي.. شعبة الخطابة تنظم مجلسًا للوعظ والإرشاد

قسم الشؤون الفكرية يواصل إقامة مسابقة النور الزكي الرمضانية في ذي قار

المجمَع العلمي يواصل إقامة 18 ختمة قرآنية رمضانية في الديوانية

المزيد

الآخبار الصحية

دراسة: تناول القهوة يوميا يخفض خطر الإصابة بالاضطرابات النفسية

عرض شائع في الفم قد يكون مرتبطا بخطر الإصابة بأمراض خطيرة

نصائح عامة لاستخدام سماعات الرأس بأمان

تأثير اللياقة البدنية على الدماغ

المزيد

الآخبار التكنلوجية

ديدان الأرض تكشف تلوث التربة بالمعادن الثقيلة

خبير أرصاد جوية: ظاهرة النينيو القادمة قد تكون الأقوى خلال 10 سنوات

"ناسا" تكشف موعد إعادة إطلاق رحلتها المأهولة إلى القمر

علماء الجيولوجيا يفكون لغز الصدع العملاق تحت الماء في المحيط الأطلسي

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength