GRAPH COLORING WITH THE FIRST-FIT ALGORITHM
David Konz · 2005
Coloring is the process of assigning a color to each vertex of a graph so neighboring vertices do not share a color. This problem is known to be NPcomplete. The First-Fit algorithm was implemented using both exhaustive and random orderings of the vertices of several graphs. Issues in implementation will be discussed. The efficiency of the First-Fit algorithm was tested exhaustively on many smaller graphs. Results of these tests and theoretical limitations will be discussed.