Фон: Пусть две вершины неориентированного графа . Множество вершин является -сепаратором, если и принадлежат различным связным компонентам . Если собственное подмножество -сепаратора является -сепаратором, то является минимальным -сепаратором. Множество вершин является (минимальным) разделителем, если существуют такие вершины , что является (минимальным) -сепаратором.
Хорошо известная теорема Дж. Дирака гласит, что граф не имеет индуцированных циклов длиной не менее четырех (называемых триангулированным или хордовым графом) тогда и только тогда, когда каждый из его минимальных разделителей является кликой. Также хорошо известно, что триангулированные графы могут быть распознаны за полиномиальное время.
Мои вопросы: что такое графики, в которых каждый минимальный разделитель является независимым множеством? Эти графики изучены? И какова сложность распознавания этих графиков? Примеры таких графиков включают деревья и циклы.