Analysis of the efficiency of graph coloring algorithms
Marek Kubale · Roczniki Polskiego Towarzystwa Matematycznego. Seria 3, Matematyka Stosowana/Matematyka Stosowana/Mathematica Applicanda · 1982
This paper discusses the computational efficiency and the number of colors used by the following algorithms for coloring vertices of graphs: sequential coloring and sequential coloring with interchange algorithms for a largest-first and a smallest-last orderings of vertices, the coloring-pairs algorithm, and the approximately maximum independent set algorithm. Each algorithm is supplied with a Pascal-like program, time complexity in terms of the size of a graph, and worst-case behaviour. In conclusion, some computational results are included with support the estimations and suggest the sequential coloring with interchange algorithm for a largest-first vertex ordering as a method which uses the least number of colors for uniformly distributed random graphs.