On the Grundy number of a graph

International audienceThe Grundy number of a graph $G$, denoted by $\Gamma (G)$, is the largest $k$ such that $G$ has a greedy $k$-colouring, that is a colouring with $k$ colours obtained by applying the greedy algorithm according to some ordering of the vertices of $G$. Trivially $\Gamma(G)\leq \Delta(G)+1$. In this paper, we show that deciding if $\Gamma(G)\leq \Delta(G)$ is NP-complete. We then show that deciding if $\Gamma(G)\geq |V(G)|-k$ is fixed parameter tractable with respect to the parameter $k$