Inequalities for the Grundy chromatic number of graphs

The Grundy (or First-Fit) chromatic number of a graph GG is the maximum number of colors used by the First-Fit coloring of the graph GG. In this paper we give upper bounds for the Grundy number of graphs in terms of vertex degrees, girth, clique partition number and for the line graphs. Next we show that if the Grundy number of a graph is large enough then the graph contains a subgraph of prescribed large girth and Grundy number.