Approximate Coloring Algorithm


Sort the verices so that degree(v(i)) >= degree( v( i+1 ) )

Colour v(0)

For i=1 to n colour v(i) so that there is no clash

Complexity O(n2)

Maximal independent set algorithm

Problem: What's the largest subset of vertices associated with V such that no pair associated with vertices defines an edge of E.
Algorithm:

Repeat until there is no vertex
Begin
Find the maximal independent set (MIS)
Reduce the graph by MIS
End

Repeat until there is no vertex
Begin
Select the vertex with the maximal degree
Include it in MIS and reduce the graph by all the adjacent nodes
End