$\mathcal{O}(VE)$ time algorithms for the Grundy (First-Fit) chromatic number of block graphs and graphs with sufficiently large girth
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910467996254208 |
|---|---|
| author | Zaker, Manouchehr |
| author_facet | Zaker, Manouchehr |
| contents | 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 $\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 $Δ_2(G)={\max}_{u\in G}~ {\max}_{v\in N(u):d(v)\leq d(u)} d(v)$. We obtain an $\mathcal{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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_00643 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | $\mathcal{O}(VE)$ time algorithms for the Grundy (First-Fit) chromatic number of block graphs and graphs with sufficiently large girth Zaker, Manouchehr Combinatorics Discrete Mathematics 05C15, 05C85 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 $\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 $Δ_2(G)={\max}_{u\in G}~ {\max}_{v\in N(u):d(v)\leq d(u)} d(v)$. We obtain an $\mathcal{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$. |
| title | $\mathcal{O}(VE)$ time algorithms for the Grundy (First-Fit) chromatic number of block graphs and graphs with sufficiently large girth |
| topic | Combinatorics Discrete Mathematics 05C15, 05C85 |
| url | https://arxiv.org/abs/2406.00643 |