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

Abstract

The Grundy (or First-Fit) chromatic number of a graph $G=(V,E)$, denoted by $\Gamma (G)$ (or ${\chi }_{{}_{\mathsf{FF}}}(G)$), is the maximum number of colors used by a First-Fit (greedy) coloring of $G$. To determine $\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$. We first obtain an $\mathcal{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 ${\Delta }_2(G)={\max }_{u\in G}{\max }_{v\in N(u):d(v)\le d(u)}d(v)$. We obtain an $\mathcal{O}(VE)$ algorithm to determine $\Gamma (G)$ for graphs $G$ whose girth $g$ is at least $2{\Delta }_2(G)+1$. 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$.

16 pages, 2 figures