Том 7, серия 1, номер 1, 2000 г., Стр. 49-66

УДК 519.17
В. В. Лозин
$E$-свободные двудольные графы

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

Лозин В. В. ¹
1. Нижегородский государственный университет,
пр. Гагарина, 23, корп. 2, 603600 Нижний Новгород, ГСП-20, Россия
е-mail: lozin@unn.ac.ru

Статья поступила 7 сентября 1999 г.