Discrete Mathematics & Theoretical Computer Science, Vol 9, No 1 (2007)

Font Size:  Small  Medium  Large

A lower bound for approximating grundy numbering

Guy Kortsarz


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