Adjacent vertex distinguishing total chromatic number of graph products

Abstract

The adjacent vertex distinguishing (AVD)-total chromatic number ${\chi }_a^{\prime \prime }(G)$ of a graph $G$ is the least integer $k$ for which $G$ has a proper total coloring $f$ with $k$ colors such that $C_G(u)\ne C_G(v)$ for every edge $uv\in E(G)$, where $C_G(u)=\{f(u)\}\cup \{f(uw):uw\in E(G)\}$. The AVD-total coloring conjecture (AVD-TCC) asserts that ${\chi }_a^{\prime \prime }(G)\le \Delta (G)+3$ for every simple graph $G$, where $\Delta (G)$ is the maximum degree of $G$. In this paper, we prove the AVD-TCC for certain classes of graph products, including Cartesian products, lexicographic products, skew products, cover products, comb products, and Indu--Bala products.

6 figures, 7 theorems