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