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