Related Problems: graph-coloring Type: Constructive algorithm Work on: Graph

Description: This selection heuristic uses a certain selection criterion for choosing the next vertex to be colored.
This strategy is better than the First Fit which simply picks a vertex from an arbitrary order.

Some strategies for selecting the next vertex to be colored have been proposed such as:
Largest degree ordering (LDO): It chooses a vertex with the highest number of neighbors.
Each vertex V contains the number of neighbors as vertex.getNumberOfNeighbors(), the algorithm hold a priority queue of the possible vertexes and chooses the first one.

Saturation degree ordering (SDO): The saturation degree of a vertex is defined as the number of its adjacent differently colored vertices. Intuitively, this heuristic provides a better coloring than LDO as it can be implemented to run in O(n^3)
Each vertex V contains the number of its adjacent differently colored vertices as vertex.getNumberOfDiffColVe(), the algorithm hold a priority queue of the possible vertexes and chooses the first one.

Incidence degree ordering (IDO): A modification of the SDO heuristic is the incidence degree ordering. The incidence degree of a vertex is defined as the number of its adjacent colored vertices. This heuristic can be implemented to run in O(n^2)

IDO+LDO: a modified version of the Largest Degree Ordering (LDO) algorithm by combining it with the Incident Degree Ordering (IDO).
The algorithm works as LDO, but when we found that there are two nodes having the same degree, theIDO was used to choose between them. There are twocriteria for chosen the vertex to be colored: (1) The number of vertices connected to the vertexLDO. (2) The number of colored vertices connected to the vertex IDO.

References: New Graph Coloring Algorithms by Dr. Hussein Al-Omari and Khair Eddin Sabri ,
A Note on First-Fit Coloring of Interval Graphs