\(\mathcal{O}(VE)\) time algorithms for the Grundy (first-fit) chromatic number of block graphs and graphs with large girth (Q6973980)

The Grundy (or First-Fit) chromatic number of a graph \(G = (V , E)\), denoted by \(\Gamma(G)\), is the maximum number of colors used by a First-Fit (greedy) coloring of \(G\). The determining \(\Gamma(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\). In this paper, the author obtains an \(\mathcal{O}(V E)\) algorithm to determine the Grundy number of block graphs, i.e. graphs in which every biconnected component is a complete graph and proves 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. It is proposed an \(\mathcal{O}(V E)\) algorithm to determine \(\Gamma(G)\) for graphs \(G\) whose girth \(g\) is at least \(2\Delta_{2}(G) + 1\), where \(\Delta_{2}(G) = \max_{u\in V} \max_{v\in N(u):d(v)\leq d(u)}d(v)\). This algorithm provides a polynomial time approximation algorithm within ratio \(\min\{1, (g +1)/(2\Delta_{2}(G)+2)\}\) for \(\Gamma(G)\) of general graphs \(G\) with girth \(g\).