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.

اخر الاخبار

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

جمعية كشافة الكفيل: المجالس الحسينية تعلّم الفتية قيم نهضة الإمام الحسين (عليه السلام)

عَبرَ المجالس الحسينية.. المجمَع العلمي يقدّم محاضرات دينية وتلاوات قرآنية في بغداد والنجف وميسان

برعاية العتبة العباسية المقدسة.. موكب قناديل السماء يُحيي مراسم اليوم الثالث عشر من المحرّم

بعد انتهاء مراسم ذكرى دفن الأجساد الطاهرة قسم رعاية الصحن يباشر بحملة تنظيف واسعة لصحن مرقد أبي الفضل العباس (عليه السلام)

المزيد

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

لكبح الجوع وخسارة الوزن.. "سر بسيط" في نظام جوكوفيتش ؟

هل يساعد الرجيم في علاج الأمراض العقلية؟

لحماية أسنان طفلك.. هذا الفيتامين يقلل خطر التسوس

أكل الطعام بسرعة.. طريق سريع إلى أمراض خطيرة

المزيد

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

ما هي أفضل درجة حرارة لتكييف الهواء في السيارة؟

ذوبان الأنهار الجليدية يوقظ "عمالقة نائمة"!

9 يوليو يشهد أقصر يوم في التاريخ المسجل ؟!!

راتبه عشرات ملايين الدولارات.. زوكربرغ يخطف "عقل أبل"

المزيد

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

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