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

Поддерево графа называется вписанным, если никакие три вершины этого поддерева не порождают треугольника в графе. Доказывается, что при любом фиксированном $k$ задача о независимом множестве разрешима за полиномиальное время для графов, входящих в один из следующих классов: 1) графы, не имеющие поддеревьев с $k$ листьями, 2) субкубические графы, не имеющие вписанных поддеревьев с $k$ листьями, 3) графы со степенями, не превосходящими $k$, не имеющие порождённых поддеревьев с 4 листьями. Ил. 1, библиогр. 12.