گراف تام

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

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

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

منابع

• الگو:Cite journal
• الگو:Cite conference
• الگو:Cite journal
• الگو:Cite journal
• الگو:Cite journal
• الگو:Cite book Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
• الگو:Cite book See especially chapter 9, "Stable Sets in Graphs", pp. 273–303.
• الگو:Cite journal
• الگو:Cite journal
• الگو:Cite conference

• الگو:یادکرد-ویکی