گراف ایده آل. Berge, Claude (1963). "Perfect graphs". Six Papers on Graph Theory. Calcutta: Indian Statistical Institute. pp. ۱–۲۱.
Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina (2005). "Recognizing Berge graphs". Combinatorica. ۲۵ (۲): ۱۴۳–۱۸۶. doi:10.1007/s00493-005-0012-8.نگهداری یادکرد:نام های متعدد:فهرست نویسندگان (link)
Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "The strong perfect graph theorem". Annals of Mathematics. 164 (۱): ۵۱–۲۲۹. doi:10.4007/annals.2006.164.51.نگهداری یادکرد:نام های متعدد:فهرست نویسندگان (link)
Gallai, Tibor (1958). "Maximum-minimum Sätze über Graphen". Acta Math. Acad. Sci. Hungar. ۹ (۳–۴): ۳۹۵–۴۳۴. doi:10.1007/BF02020271.
Golumbic, Martin Charles (1980). "Algorithmic Graph Theory and Perfect Graphs". Academic Press. شابک ۰-۴۴۴-۵۱۵۳۰-۵. Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
Grötschel, Martin; Lovász, László; Schrijver, Alexander (1988). "Geometric Algorithms and Combinatorial Optimization". Springer-Verlag.. See especially chapter 9, "Stable Sets in Graphs", pp. ۲۷۳–۳۰۳.
Lovász, László (1972). "Normal hypergraphs and the perfect graph conjecture". Discrete Mathematics. ۲ (۳): ۲۵۳–۲۶۷. doi:10.1016/0012-365X(72)90006-4.
Lovász, László (1972). "A characterization of perfect graphs". Journal of Combinatorial Theory, Series B. ۱۳ (۲): ۹۵–۹۸. doi:10.1016/0095-8956(72)90045-7.
Lovász, László (1983). "Perfect graphs". In Beineke, Lowell W. ; Wilson, Robin J. (Eds.). Selected Topics in Graph Theory, Vol. 2. Academic Press. pp. ۵۵–۸۷. شابک ۰-۱۲-۰۸۶۲۰۲-۶.نگهداری یادکرد:نام های متعدد:فهرست ویراستاران (link) نگهداری یادکرد:متن اضافی:فهرست ویراستاران (link)
در تئوری گراف، یک گراف آرمانی گرافی است که رنگ آمیزی گراف هر زیر گراف القایی، برابر سایز بزرگترین گروه آن زیرگراف باشد. در سایهٔ تئوری قوی گراف آرمانی، از سال ۲۰۰۲ می دانیم که گراف های آرمانی همانند گراف های برگ هستند. گراف G یک گراف برگ است اگر خود گراف G یا مکملش یک دورالقایی به طول فرد حداقل ۵ داشته باشد.
گراف های آرمانی دربرگیرندهٔ تعداد زیادی دسته های مهم گراف ها هستند و در یکی کردن نتایج مربوط به رنگ آمیزی ها و گروه ها در آن دسته ها، بکار می روند. به عنوان مثال در همهٔ گراف های آرمانی مسئله ی رنگ آمیزی گراف، مسئله ی بزرگترین گروه و مسئله ی بزرگترین مجموعه ی مستقل همگی در زمان چند جمله ای بدست می آیند. علاوه بر این، برخی از تئوری های مهم کوچکترین-بزرگترین در ترکیبات، مانند تئوری Dilworth می توانند در قالب ایده آل کردن گراف متناظرشان بیان شوند.نظریهٔ گراف ایده آل از سال ۱۹۵۸ به وسیلهٔ Tibor Gallai گسترش پیدا کرد، نتیجهٔ کار او را می توان اینگونه تعبیر کرد که مکمل گراف دوبخشی ایده آل است؛ این نتیجه نیز می تواند به عنوان یک معادل ساده از نظریه König دانست. برآمدی خیلی قدیمی تر که با تطابق و پوشش راسی در گراف های دو بخشی مرتبط بود. اولین استفادهٔ واژهٔ گراف آرمانی به نظر می رسد در یک مقاله ۱۹۶۳ از کلود برگ است و پس از آن گراف برگ نامیده شد. در این مقاله او نتیجهٔ Gallai را با برخی از نتایج مشابه، به وسیلهٔ تعریف گراف آرمانی یکی کرد و برابری گراف ایده آل و گراف برگ را حدس زد. حدس برگ در سال ۲۰۰۲ به عنوان نظریه ی قوی گراف آرمانی ثابت شده است.
بعضی از گراف های ایده آل آشنا تر:گراف دو بخشی: گرافی که می تواند با دو رنگ، رنگ آمیزی(گراف) شود؛ مانند درخت (تئوری گراف)، گراف های بدون دور.گراف خطی از گراف های دو قسمتی (ر.ک. نظریه کونیگ) گراف رخ (گراف خطی از گراف های کامل دو بخشی) یک مورد خاص است.
Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina (2005). "Recognizing Berge graphs". Combinatorica. ۲۵ (۲): ۱۴۳–۱۸۶. doi:10.1007/s00493-005-0012-8.نگهداری یادکرد:نام های متعدد:فهرست نویسندگان (link)
Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "The strong perfect graph theorem". Annals of Mathematics. 164 (۱): ۵۱–۲۲۹. doi:10.4007/annals.2006.164.51.نگهداری یادکرد:نام های متعدد:فهرست نویسندگان (link)
Gallai, Tibor (1958). "Maximum-minimum Sätze über Graphen". Acta Math. Acad. Sci. Hungar. ۹ (۳–۴): ۳۹۵–۴۳۴. doi:10.1007/BF02020271.
Golumbic, Martin Charles (1980). "Algorithmic Graph Theory and Perfect Graphs". Academic Press. شابک ۰-۴۴۴-۵۱۵۳۰-۵. Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
Grötschel, Martin; Lovász, László; Schrijver, Alexander (1988). "Geometric Algorithms and Combinatorial Optimization". Springer-Verlag.. See especially chapter 9, "Stable Sets in Graphs", pp. ۲۷۳–۳۰۳.
Lovász, László (1972). "Normal hypergraphs and the perfect graph conjecture". Discrete Mathematics. ۲ (۳): ۲۵۳–۲۶۷. doi:10.1016/0012-365X(72)90006-4.
Lovász, László (1972). "A characterization of perfect graphs". Journal of Combinatorial Theory, Series B. ۱۳ (۲): ۹۵–۹۸. doi:10.1016/0095-8956(72)90045-7.
Lovász, László (1983). "Perfect graphs". In Beineke, Lowell W. ; Wilson, Robin J. (Eds.). Selected Topics in Graph Theory, Vol. 2. Academic Press. pp. ۵۵–۸۷. شابک ۰-۱۲-۰۸۶۲۰۲-۶.نگهداری یادکرد:نام های متعدد:فهرست ویراستاران (link) نگهداری یادکرد:متن اضافی:فهرست ویراستاران (link)
در تئوری گراف، یک گراف آرمانی گرافی است که رنگ آمیزی گراف هر زیر گراف القایی، برابر سایز بزرگترین گروه آن زیرگراف باشد. در سایهٔ تئوری قوی گراف آرمانی، از سال ۲۰۰۲ می دانیم که گراف های آرمانی همانند گراف های برگ هستند. گراف G یک گراف برگ است اگر خود گراف G یا مکملش یک دورالقایی به طول فرد حداقل ۵ داشته باشد.
گراف های آرمانی دربرگیرندهٔ تعداد زیادی دسته های مهم گراف ها هستند و در یکی کردن نتایج مربوط به رنگ آمیزی ها و گروه ها در آن دسته ها، بکار می روند. به عنوان مثال در همهٔ گراف های آرمانی مسئله ی رنگ آمیزی گراف، مسئله ی بزرگترین گروه و مسئله ی بزرگترین مجموعه ی مستقل همگی در زمان چند جمله ای بدست می آیند. علاوه بر این، برخی از تئوری های مهم کوچکترین-بزرگترین در ترکیبات، مانند تئوری Dilworth می توانند در قالب ایده آل کردن گراف متناظرشان بیان شوند.نظریهٔ گراف ایده آل از سال ۱۹۵۸ به وسیلهٔ Tibor Gallai گسترش پیدا کرد، نتیجهٔ کار او را می توان اینگونه تعبیر کرد که مکمل گراف دوبخشی ایده آل است؛ این نتیجه نیز می تواند به عنوان یک معادل ساده از نظریه König دانست. برآمدی خیلی قدیمی تر که با تطابق و پوشش راسی در گراف های دو بخشی مرتبط بود. اولین استفادهٔ واژهٔ گراف آرمانی به نظر می رسد در یک مقاله ۱۹۶۳ از کلود برگ است و پس از آن گراف برگ نامیده شد. در این مقاله او نتیجهٔ Gallai را با برخی از نتایج مشابه، به وسیلهٔ تعریف گراف آرمانی یکی کرد و برابری گراف ایده آل و گراف برگ را حدس زد. حدس برگ در سال ۲۰۰۲ به عنوان نظریه ی قوی گراف آرمانی ثابت شده است.
بعضی از گراف های ایده آل آشنا تر:گراف دو بخشی: گرافی که می تواند با دو رنگ، رنگ آمیزی(گراف) شود؛ مانند درخت (تئوری گراف)، گراف های بدون دور.گراف خطی از گراف های دو قسمتی (ر.ک. نظریه کونیگ) گراف رخ (گراف خطی از گراف های کامل دو بخشی) یک مورد خاص است.
wiki: گراف ایده آل