گراف تام

در نظریه گراف، گراف تام ، گرافی است که عدد رنگی آن برای هر زیرگراف القایی اش برابر با مرتبه بزرگترین کلیک آن زیرگراف (عدد کلیکی) باشد. به‌طور معادل می‌توان تعریف اخیر را برحسب نمادها بیان نماد: گراف دلخواهی چون  تام است اگر و تنها اگر برای تمام  داشته باشیم .

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

منابع 

 
 
 
 
 
  Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
  See especially chapter 9, "Stable Sets in Graphs", pp. 273–303.
 
 
 

 

گراف‌های تام