Recursive largest first algorithm

The Recursive Largest First (RLF) algorithm is a <a href="/facts/Heuristic/BcBEkv9c">heuristic</a> for the <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a> <a href="/facts/Graph_coloring_problem/J6HoBfP0">graph coloring problem</a>. It was originally proposed by Frank Leighton in 1979.
The RLF algorithm assigns colors to a graph’s vertices by constructing each color class one at a time. It does this by identifying a <a href="/facts/Maximal_independent_set/eB4NQsny">maximal independent set</a> of vertices in the graph, assigning these to the same color, and then removing these vertices from the graph. These actions are repeated on the remaining subgraph until no vertices remain. 
To form high-quality solutions (solutions using few colors), the RLF algorithm uses specialized heuristic rules to try to identify "good quality" independent sets. These heuristics make the RLF algorithm exact for <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite</a>, <a href="/facts/Cycle_graph/bYhnPDHc">cycle</a>, and <a href="/facts/Wheel_graph/rrQQSxNw">wheel graphs</a>. In general, however, the algorithm is approximate and may well return solutions that use more colors than the graph’s <a href="/facts/Chromatic_number/J6HoBfP0">chromatic number</a>.

Recursive largest first algorithm open-in-new

Recursive largest first algorithm