Abstract:
The idea of $\omega$-perfect graph is introduced. Several classes of $\omega$-perfect graphs are described, but the question on describing of the whole class of $\omega$-perfect graphs is not clear yet. Vertices colouring algorithm is suggested for graphs containing no even number of holes, where the number of used colours does not overwhelm the double chromatic number.