Граф О называют г-хроматическим, если его вершины могут быть раскрашены с использованием г цветов ( красок) так, что не найдется двух смежных вершин одного цвета. Задача нахождения хроматического числа графа называется задачей о раскраске ( или задачей раскраски) графа. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на г подмножеств, каждое из которых содержит вершины одного цвета. Эти множества являются независимыми, поскольку в пределах одного множества нет двух смежных вершин.