On Grundy and b-chromatic number of some families of graphs: a comparative study

Abstract

The Grundy and the {\rm b}-chromatic number of graphs are two important chromatic parameters. The Grundy number of a graph $G$, denoted by $\Gamma (G)$ is the worst case behavior of greedy (First-Fit) coloring procedure for $G$ and the {\rm b}-chromatic number $\mathrm{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\ge 1}$ with limited {\rm b}-chromatic number but $\Gamma (G_n)\to \infty$. We obtain families of graphs $\mathcal{F}$ such that for some adequate function $f(.)$, $\Gamma (G)\le f(\mathrm{b}(G))$, for each graph $G$ from the family. This verifies a previous conjecture for these families.

Accepted version to be published in Graphs and Combinatorics

Cited by in corpus (1)

• On b-acyclic chromatic number of a graph