The Grundy number of a graph G, denoted by Γ(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 vertexes of G. The b‐chromatic number of a graph G, denoted by χ
b
(G), is the largest k such that G has a b‐colouring with k colours, that is a colouring in which each colour class contains a b‐vertex, a vertex with neighbours in all other colour classes. Trivially χ
b
(G),Γ(G)≤Δ(G)+1. In this paper, we show that deciding if Γ(G)≤Δ(G) is NP‐complete even for a bipartite graph G. We then show that deciding if Γ(G)≥|V(G)|−k or if χ
b
(G)≥|V(G)|−k are fixed parameter tractable problems with respect to the parameter k.
