Характеризация хорошо укрытых графов в терминах запрещенных костабильных подграфов

Abstract

Граф называется хорошо укрытым, если каждое максимальное независимое множество является наибольшим. Пусть $I$ – независимое множество (возможно, пустое) в графе $G$. Подграф графа $G$, полученный удалением множества $I$ вместе с окрестностью, называется костабильным. Получена характеризация класса хорошо укрытых графов в терминах минимального множества запрещенных костабильных подграфов. Из нее вытекают характеризации известных подклассов класса хорошо укрытых графов и существование полиномиального алгоритма распознавания хорошо укрытых графов с ограниченными степенями вершин.