Editing Graph coloring (section)

=== Heuristic algorithms ===
Two well-known polynomial-time heuristics for graph colouring are the [[DSatur]] and [[Recursive largest first algorithm|recursive largest first]] (RLF) algorithms.

Similarly to the [[Greedy coloring|greedy colouring algorithm]], DSatur colours the [[Vertex (graph theory)|vertices]] of a [[Graph (graph theory)|graph]] one after another, expending a previously unused colour when needed. Once a new [[Vertex (graph theory)|vertex]] has been coloured, the algorithm determines which of the remaining uncoloured vertices has the highest number of different colours in its neighbourhood and colours this vertex next. This is defined as the ''degree of saturation'' of a given vertex.

The [[recursive largest first algorithm]] operates in a different fashion by constructing each color class one at a time. It does this by identifying a [[maximal independent set]] of vertices in the graph using specialised heuristic rules. It then assigns these vertices to the same color and removes them from the graph. These actions are repeated on the remaining subgraph until no vertices remain.

The worst-case complexity of DSatur is <math>O(n^2)</math>, where <math>n</math> is the number of vertices in the graph. The algorithm can also be implemented using a binary heap to store saturation degrees, operating in <math>O((n+m)\log n)</math> where <math>m</math> is the number of edges in the graph.{{sfnp|Lewis|2021}} This produces much faster runs with sparse graphs. The overall complexity of RLF is slightly higher than [[DSatur]] at <math>O(mn)</math>.{{sfnp|Lewis|2021}}

DSatur and RLF are [[Exact algorithm|exact]] for [[bipartite graph|bipartite]], [[cycle graph|cycle]], and [[wheel graph]]s.{{sfnp|Lewis|2021}}