2.1. Нижние оценки для .

Поскольку число равно мощности наибольшего множества попарно несмежных вершин графа G, то оно совпадает также с мощностью наибольшего множества вершин в G, которые могут быть окрашены в один цвет, и, следовательно,

, (1)

где n — число вершин графа G, а обозначает наибольшее целое число, не превосходящее числа x.

Еще одна нижняя оценка для предложена Геллером:

. (2)