Разбиение множества вершин двудольного графа наименьшим числом полных двудольных подграфов

Abstract

Изучается вычислительная сложность следующей задачи распознавания: для заданного графа и натурального k требуется ответить на вопрос: можно ли разбить множество вершин этого графа на не более чем k связных полных двудольных подграфов. Известно, что эта задача является NP-полной в классе двудольных графов. Установлено, что рассматриваемая задача является полиноми- ально разрешимой в классах двудольных дистанционно-наследуемых графов, двудольных перестановочных графов и остается NP-полной для двудольных графов с совершенным исключением, C4-свободных двудольных графов.