گراف شکافته

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

ممکن است گراف شکافته شده بیش از یک افراز به کلیک و مجموعه مستقل داشته باشد؛ به عنوان مثال، مسیر a-b-c گراف شکافته شده‌ای است که رئوس آن را می‌توان به سه روش مختلف افراز نمود:
 کلیک  و مجموعه مستقل 
 کلیک  و مجموعه مستقل 
 کلیک  و مجموعه مستقل 
گراف‌های شکافته شده را می‌توان برحسب زیرگراف های القاء شده ممنوعه شان مشخصه سازی نمود: یک گراف دلخواه شکافته شده‌است اگر و تنها اگر هیچ زیرگراف القاء شده آن که چهار یا پنج رأس داشته یا دارای یک جفت یال مجزا باشد (متمم یک ۴-دور)، دوری نباشد.

ارجاعات

منابع 

 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 
 .
 . Translated as "Yet another method of enumerating unmarked combinatorial objects" (1990), Mathematical notes of the Academy of Sciences of the USSR 48 (6): 1239–1245, .
 .
 .

برای مطالعه بیشتر 

 A chapter on split graphs appears in the book by Martin Charles Golumbic, "Algorithmic Graph Theory and Perfect Graphs".

خانواده‌های گراف
رده‌های تقاطعی گراف‌ها
گراف‌های تام