Inequalities for the Grundy chromatic number of graphs Original Research Article

The Grundy (or First-Fit) chromatic number of a graph image is the maximum number of colors used by the First-Fit coloring of the graph image. 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.