%0 Journal Article
%T A lower bound for approximating grundy numbering
%A Guy Kortsarz
%J Discrete Mathematics & Theoretical Computer Science
%D 2007
%I Discrete Mathematics & Theoretical Computer Science
%X The grundy numbering 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 numbering problem is to find this ordering. We prove that there is a constant c>1 so that approximating the grundy numbering problem within c is not possible, unless NP   RP
%U http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/625