$\omega$-совершенные графы

Введено понятие $\omega$-совершенного графа. Описаны некоторые классы $\omega$-совершенных графов; вопрос описания полного класса $\omega$-совершенных графов пока открыт. Предложен алгоритм раскраски вершин графа, при котором число используемых красок для графов, не содержащих четных дырок, не превосходит удвоенного хроматического числа.