A lower bound for approximating the grundy number

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

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

Original languageEnglish (US)
Pages (from-to)7-22
Number of pages16
JournalDiscrete Mathematics and Theoretical Computer Science
Volume9
Issue number1
StatePublished - Jan 26 2007

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)
  • Discrete Mathematics and Combinatorics

Keywords

  • Approximation
  • Coloring
  • Grundy
  • Hardness
  • Number

Fingerprint Dive into the research topics of 'A lower bound for approximating the grundy number'. Together they form a unique fingerprint.

  • Cite this