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) \neq 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 \leq \chi_t(G) \leq \Delta(G) + 2\). \(G\) is called Type 1 (resp. Type 2) if \(\chi_t(G) = \Delta(G) + 1\) (resp. \(\chi_t(G) = \Delta(G) + 2\)). In this paper, we prove that the augmented cube \(AQ_n\) is of Type 1 for \(n \geq 4\). We also consider the adjacent vertex-distinguishing total chromatic number of \(AQ_n\) and prove that \(\chi_{at}(AQ_n) = \Delta(AQ_n) + 2\) for \(n \geq 3 \).