Spremljeno u:
| Glavni autori: | , |
|---|---|
| Format: | Preprint |
| Izdano: |
2020
|
| Teme: | |
| Online pristup: | https://arxiv.org/abs/2012.10070 |
| Oznake: |
Dodaj oznaku
Bez oznaka, Budi prvi tko označuje ovaj zapis!
|
Sadržaj:
- The Grundy and the {\rm b}-chromatic number of graphs are two important chromatic parameters. The Grundy number of a graph $G$, denoted by $Γ(G)$ is the worst case behavior of greedy (First-Fit) coloring procedure for $G$ and the {\rm b}-chromatic number ${\rm{b}}(G)$ is the maximum number of colors used in any color-dominating coloring of $G$. Because the nature of these colorings are different they have been studied widely but separately in the literature. This paper presents a comparative study of these coloring parameters. There exists a sequence $\{G_n\}_{n\geq 1}$ with limited {\rm b}-chromatic number but $Γ(G_n)\rightarrow \infty$. We obtain families of graphs $\mathcal{F}$ such that for some adequate function $f(.)$, $Γ(G)\leq f({\rm{b}}(G))$, for each graph $G$ from the family. This verifies a previous conjecture for these families.