A lower bound for approximating the grundy number

The grundy number of a graph is the maximum number of colors used by on-line first-fit coloring, under the worst order of arrival of vertices. The grundy number problem is to find this ordering. We prove that there is a constant c > 1 so that approximating the grundy number problem within c is not possible, unless NP ⊆ RP