расщепляемый граф

В теории графов расщепляемым графом называется граф, в котором вершины можно разделить на клику и независимое множество. Расщепляемые графы впервые изучали Фёлдес и Хаммер, и независимо ввели Тышкевич и Черняк. Расщепляемый граф может иметь несколько разложений на клику и независимое множество. Так, путь a-b-c является расщепляемым и может быть разбит тремя разными способами: 1. * клика {a,b} и независимое множество {c} 2. * клика {b,c} и независимое множество {a} 3. * клика {b} и независимое множество {a,c} Расщепляемые графы можно охарактеризовать в терминах их запрещённых подграфов — граф расщепляем в том и только в том случае, когда никакой порождённый подграф не является циклом с четырьмя или пятью вершинами, а также нет пары несвязных вершин (то есть дополнения цикла из 4 вершин).