$E$-свободные двудольные графы

Предложена структурная характеризация класса двудольных графов, не содержащих порожденных подграфов, изоморфных графу $E$, где $E$ – граф с вершинами $a$, $b$, $c$, $d$, $e$, $f$ и ребрами $ab$, $bc$, $cd$, $de$, $cf$. Показано, что графы из этого класса распознаются за время $O(n^2)$. Доказана полиномиальная разрешимость в данном классе ряда проблем, являющихся NP-полными на множестве всех двудольных графов. Ил. 3, библиогр. 27.