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
Belmonte, RĂŠmy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota, 2022, Grundy Distinguishes Treewidth From Pathwidth, SIAM Journal On Discrete Mathematics, 36, 3, pp. 1761-1787, 10.1137/20m1385779.
Bonnet, Ădouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian, 2015, Complexity Of Grundy Coloring And Its Variants, Lecture Notes In Computer Science, pp. 109-120, 10.1007/978-3-319-21398-9_9.