On acyclic b-chromatic number of cubic graphs

Abstract

Let $G$ be a graph. An acyclic $k$-coloring of $G$ is a map $c:V(G)\to \{1,\dots ,k\}$ such that $c(u)\ne c(v)$ for any $uv\in E(G)$ and the subgraph induced by the vertices of any two colors $i,j\in \{1,\dots ,k\}$ is a forest. If every vertex $v$ of a color class $V_i$ misses a color ${\ell }_v\in \{1,\dots ,k\}$ in its closed neighborhood, then every $v\in V_i$ can be recolored with ${\ell }_v$ and we obtain a $(k-1)$-coloring of $G$. If a new coloring $c^{\prime }$ is also acyclic, then such a recoloring is an acyclic recoloring step and $c^{\prime }$ is in relation ${◃}_a$ with $c$. The acyclic b-chromatic number $A_b(G)$ of $G$ is the maximum number of colors in an acyclic coloring where no acyclic recoloring step is possible. Equivalently, it is the maximum number of colors in a minimum element of the transitive closure of ${◃}_a$. In this paper, we consider $A_b(G)$ of cubic graphs.