### A lower bound for approximating grundy numbering

*Guy Kortsarz*

#### Abstract

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

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page