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 language | English (US) |
|---|---|
| Pages (from-to) | 7-22 |
| Number of pages | 16 |
| Journal | Discrete Mathematics and Theoretical Computer Science |
| Volume | 9 |
| Issue number | 1 |
| State | Published - 2007 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- General Computer Science
- Discrete Mathematics and Combinatorics
Keywords
- Approximation
- Coloring
- Grundy
- Hardness
- Number