On the Grundy and b-Chromatic Numbers of a Graph

The Grundy number of a graph G, denoted by I"(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 chi (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 chi (b) (G),I"(G)a parts per thousand currency sign Delta(G)+1. In this paper, we show that deciding if I"(G)a parts per thousand currency sign Delta(G) is NP-complete even for a bipartite graph G. We then show that deciding if I"(G)a parts per thousand yen|V(G)|-k or if chi (b) (G)a parts per thousand yen|V(G)|-k are fixed parameter tractable problems with respect to the parameter k.