Key points are not available for this paper at this time.
The Grundy (or First-Fit) chromatic number of a graph G= (V, E), denoted by (G) (or _ ₅₅ (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) =ₔ ₆~ ₕ ₍ (ₔ): ₃ (ₕ) ₃ (ₔ) 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 \1, (g+1) / (2₂ (G) +2) \ for (G) of general graphs G with girth g.
Manouchehr Zaker (Sun,) studied this question.