A note on the adjacent vertex distinguishing total chromatic number of graphs (Q1759396)

Adjacent vertex distinguishing total coloring of given graph \(G\) is a coloring \(\phi :V(G) \cup E(G) \rightarrow \{1,2,\dots,k\}\) such that \(\phi(x) \neq \phi(y)\) for any adjacent or incident elements \(x,y \in V(G) \cup E(G)\) and moreover \(C_\phi(x) \neq C_\phi(y)\) for any adjacent vertices \(x\) and \(y\), where \(C_\phi(x) = \{\phi(xy) \mid xy \in E(G)\} \cup \{\phi(x)\}\). Adjacent vertex distinguishing total chromatic number \(\chi''_a(G)\) is the smallest value of \(k\) for which such a coloring exists. In the main theorem the authors prove that \(\chi''_a(G) \leq 2\Delta(G)\) for all the graphs with \(\Delta \geq 3\). It is the partial confirmation of the conjecture formulated in [\textit{Z. Zhang} et al., Sci. China, Ser. A, 48, No.\,3, 289--299 (2005; Zbl 1080.05036)], stating that \(\chi''_a(G) \leq \Delta(G)+3\) for non-trivial connected graphs. This theorem generalizes the results of \textit{X. Chen} [Discrete Math. 308, No.\,17, 4003--4007 (2008; Zbl 1203.05052)], \textit{J. Hulgan} [Discrete Math. 309, No.\,8, 2548--2550 (2009; Zbl 1221.05143)], and \textit{H. Wang} [J. Comb. Optim. 14, No.\,1, 87--109 (2007; Zbl 1125.05043)]. It also improves the inequality \(\chi''_a(G) \leq \Delta(G)+c\) proved in [\textit{T. Coker} and \textit{K. Johannson}, Discrete Math. 312, No.\,17, 2741--2750 (2012; Zbl 1245.05042)] for graphs with relatively small values of \(\Delta(G)\).