Total and Adjacent Vertex-Distinguishing Total Chromatic Numbers of Augmented Cubes

Abstract

A total coloring of a graph $G$ is a coloring of both the edges and the vertices. A total coloring is proper if no two adjacent or incident elements receive the same color. An adjacent vertex-distinguishing total coloring $h$ of a simple graph $G=(V,E)$ is a proper total coloring of $G$ such that $H(u)\ne H(v)$ for any two adjacent vertices $u$ and $v$, where $H(u)=\{h(wu)\mid wu\in E(G)\}\cup \{h(u)\}$ and $H(v)=\{h(xv)\mid xv\in E(G)\}\cup \{h(v)\}$. The minimum number of colors required for a proper total coloring (resp. an adjacent vertex-distinguishing total coloring) of $G$ is called the total chromatic number (resp. adjacent vertex-distinguishing total chromatic number) of $G$ and denoted by ${\chi }_t(G)$ (resp. ${\chi }_{at}(G)$). The Total Coloring Conjecture (TCC) states that for every simple graph $G$, $\chi (G)+1\le {\chi }_t(G)\le \mathrm{\Delta }(G)+2$. $G$ is called Type 1 (resp. Type 2) if ${\chi }_t(G)=\mathrm{\Delta }(G)+1$ (resp. ${\chi }_t(G)=\mathrm{\Delta }(G)+2$). In this paper, we prove that the augmented cube $A{Q}_n$ is of Type 1 for $n\ge 4$. We also consider the adjacent vertex-distinguishing total chromatic number of $A{Q}_n$ and prove that ${\chi }_{at}(A{Q}_n)=\mathrm{\Delta }(A{Q}_n)+2$ for $n\ge 3$.