O(VE) time algorithms for the Grundy (First-Fit) chromatic number of block graphs and graphs with sufficiently large girth

The Grundy (or First-Fit) chromatic number of a graph $G=(V,E)$, denoted by Γ(G) (or χ_FF(G)), is the maximum number of colors used by a First-Fit (greedy) coloring of G. To determine Γ(G) is NP-complete for various classes of graphs. Also there exists a constant $c>0$ such that the Grundy number is hard to approximate within the ratio c. We first obtain an O(VE) algorithm to determine the Grundy number of block graphs i.e. graphs in which every biconnected component is complete subgraph. We prove that the Grundy number of a general graph G with cut-vertices is upper bounded by the Grundy number of a block graph corresponding to G. This provides a reasonable upper bound for the Grundy number of graphs with cut-vertices. Next, define Δ₂(G)=maxu∈ G~ maxv∈ N(u):d(v)≤ d(u) d(v). We obtain an O(VE) algorithm to determine Γ(G) for graphs G whose girth g is at least 2Δ₂(G)+1. This algorithm provides a polynomial time approximation algorithm within ratio min \1, (g+1)/(2Δ₂(G)+2)\ for Γ(G) of general graphs G with girth g.