Graph coloring is the process of assigning colors to the vertices of a graph such that no two adjacent vertices have the same color. The smallest number of colors needed to color a graph is called the chromatic number. Due to the NP-Hard nature of this problem, we are interested in algorithms that approximate the chromatic number. This paper describes a new algorithm for approximating the chromatic number that is shown to outperform existing greedy algorithms in experimental results.