3. Приближенные алгоритмы раскрашивания.
Существует много эвристических процедур раскрашивания графов, позволяющих находить хорошие приближения для хроматического числа графа в тех случаях, когда размеры графа слишком велики и получение оптимальной раскраски точными методами, упоминавшимися ранее, затруднительно.
В настоящем разделе дается краткое описание одной из таких процедур и ряда ее разновидностей. Данная процедура относится к последовательным методам, основанным на упорядочивании множества вершин.В этом простейшем из методов вершины вначале располагаются в порядке невозрастания их степеней. Первая вершина окрашивается в цвет 1; затем список вершин просматривается сверху вниз (по невозрастанию степеней) и в цвет 1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Потом возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет 2 и снова просматриваем список вершин сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину, которая но соединена ребром с другой, уже окрашенной в цвет 2 вершиной. Аналогично действуем с цветами 3, 4 и т.д., пока не будут окрашены все вершины. Число использованных цветов будет тогда приближенным значением хроматического числа графа.
Простая модификация описанной выше эвристической процедуры состоит в переупорядочивании неокрашенных вершин после окраски каждой очередной вершины: оставшиеся неокрашенные вершины записываются в порядке невозрастания их «относительных» степеней, т.е. степеней в таком графе, который получается из данного после удаления окрашенных вершин (вместе с ребрами, инцидентными удаленным вершинам).
В этой процедуре молчаливо предполагалось, что если две вершины имеют одинаковые степени, то их взаимное положение в списке случайно. В таких ситуациях уточнение в размещении вершин можно осуществлять с помощью двухшаговых степеней 
вершин 
, имеющих одинаковые степени (одинаковые 1-шаговые степени), где определяется как число маршрутов длины 2. исходящих из .
. Если все-таки найдутся вершины, у которых совпадают и степени 
, и степени , то можно вычислить трехшаговые степени 
(определяемые аналогичным образом) и разместить вершины с учетом степеней и т.д. Можно действовать иначе: размещать вершины сразу в соответствии с их степенями или степенями и применять тот же самый последовательный метод раскраски. Таким образом, описанный выше метод раскрашивания очерчивает целый класс последовательных методов, каждый из которых связан с определенным способом упорядочивания вершин, либо статическим, т.е. фиксированным сразу для всей процедуры, либо динамическим, т.е. изменяющимся в процессе раскраски. Способ упорядочивания может базироваться на многих возможных критериях, зависящих от степеней вершин или от каких-либо других родственных характеристик. Результаты вычислении и сравнение последовательных методов раскрашивания для графов, выбранных случайным образом, приведены в работах Матулы, Марбле и Исааксона и Вильямса. Границы применимости этих эвристических методов демонстрируются у Митчема, показавшего, что можно построить графы, для которых любой из эвристических методов дает произвольно плохие оценки хроматического числа.