Аннотация:
Введено понятие $\omega$-совершенного графа. Описаны некоторые классы $\omega$-совершенных графов; вопрос описания полного класса $\omega$-совершенных графов пока открыт. Предложен алгоритм раскраски вершин графа, при котором число используемых красок для графов, не содержащих четных дырок, не превосходит удвоенного хроматического числа.
УДК:519.1
Поступила в редакцию: 02.06.1986 Принята в печать: 30.09.1987