2024/06/02 by Manouchehr Zaker, Zaker, Manouchehr
Computer Science · Mathematics · #05C15 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2406.00643
openalex publication_date 2024/06/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Grundy (or First-Fit) chromatic number of a graph G=(V,E), denoted by Γ(G) (or χ_\sf 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 Δ2(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Δ2(G)+1. This algorithm provides a polynomial time approximation algorithm within ratio min \1, (g+1)/(2Δ2(G)+2)\ for Γ(G) of general graphs G with girth g.