گراف تام

در نظریه گراف، گراف تام (به انگلیسی: Perfect Graph)، گرافی است که عدد رنگی آن برای هر زیرگراف القایی اش برابر با مرتبه بزرگترین کلیک آن زیرگراف (عدد کلیکی) باشد. به‌طور معادل می‌توان تعریف اخیر را برحسب نمادها بیان نماد: گراف دلخواهی چون $G=(V,E)$

تام است اگر و تنها اگر برای تمام

S\subseteq V

داشته باشیم

\chi (G[S])=\omega (G[S])

.

گراف پالی از مرتبه ۹ که با سه رنگ، رنگ‌آمیزی شده و کلیک سه رأسی را نشان می‌دهد. در این گراف و هر کدام از زیرگراف‌های القایی آن، عدد رنگی برابر با عدد کلیکی است، لذا گراف تامی می‌باشد.

گراف‌های تام شامل خانواده‌های مهم بسیاری از گراف‌ها بوده و موجب اتحاد و یکی شدن نتایج رنگ‌آمیزی‌ها و کلیک‌های مرتبط در آن خانواده‌ها می‌گردد. به عنوان مثال، در تمام گراف‌های تام، مسئله رنگ‌آمیزی گراف، مسئله کلیک ماکسیمم و مسئله مجموعه مستقل ماکسیمم را می‌توان به صورت زمان-چندجمله‌ای حل نمود. به علاوه، قضایای متعدد و مهم ترکیبیاتی از نوع مین-مکس، همچون قضیه دیلورث را می‌توان برحسب تام سازی گراف‌های خاصی بیان نمود.

منابع

Berge, Claude (1961). "Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind". Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math. -Natur. Reihe. 10: 114.
Berge, Claude (1963). "Perfect graphs". Six Papers on Graph Theory. Calcutta: Indian Statistical Institute. pp. 1–21.
Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina (2005). "Recognizing Berge graphs". Combinatorica. 25 (2): 143–186. doi:10.1007/s00493-005-0012-8. S2CID 2229369.
Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "The strong perfect graph theorem". Annals of Mathematics. 164 (1): 51–229. arXiv:math/0212070. doi:10.4007/annals.2006.164.51. S2CID 119151552.
Gallai, Tibor (1958). "Maximum-minimum Sätze über Graphen". Acta Math. Acad. Sci. Hung. 9 (3–4): 395–434. doi:10.1007/BF02020271. S2CID 123953062.
Golumbic, Martin Charles (1980). Algorithmic Graph Theory and Perfect Graphs. Academic Press. ISBN 0-444-51530-5. Archived from the original on 2010-05-22. Retrieved 2007-11-21. 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. 273–303.
Lovász, László (1972). "Normal hypergraphs and the perfect graph conjecture". Discrete Mathematics. 2 (3): 253–267. doi:10.1016/0012-365X(72)90006-4.
Lovász, László (1972). "A characterization of perfect graphs". Journal of Combinatorial Theory. Series B. 13 (2): 95–98. 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. 55–87. ISBN 0-12-086202-6.