Новые случаи полиномиальной разрешимости задачи о независимом множестве для графов с запрещёнными триодами

Триод  — это дерево с тремя листьями и единственной вершиной степени $3$. Задача о независимом множестве разрешима за полиномиальное время для графов, не содержащих в качестве подграфа триод с любым фиксированным числом вершин. Если же запрещается порождённый триод с $k$ вершинами, то при $k>5$ сложность решения этой задачи неизвестна. В статье рассматриваются промежуточные случаи, когда запрещаются порождённый триод с любым фиксированным числом вершин и некоторые его надграфы. Для произвольного триода с фиксированным числом вершин доказана разрешимость задачи о независимом множестве за полиномиальное время в следующих случаях:

• запрещаются триод и все его остовные надграфы с ограниченными степенями вершин;
• запрещаются триод и все его остовные надграфы с большим дефицитом (числом рёбер в дополнительном графе);
• запрещаются триод и все его надграфы, из которых с помощью операции пересечения графов можно получить этот триод, а в самом графе есть вершина с ограниченной антистепенью.

Библиогр. 20.