A note on the adjacent vertex distinguishing total chromatic number of graphs. (English) Zbl 1258.05037

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 [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 X. Chen [Discrete Math. 308, No.17, 4003–4007 (2008; Zbl 1203.05052)], J. Hulgan [Discrete Math. 309, No.8, 2548–2550 (2009; Zbl 1221.05143)], and 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 [T. Coker and K. Johannson, Discrete Math. 312, No.17, 2741–2750 (2012; Zbl 1245.05042)] for graphs with relatively small values of \(\Delta(G)\).


05C15 Coloring of graphs and hypergraphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
Full Text: DOI


[2] Chen, X., On the adjacent vertex distinguishing total coloring numbers of graphs with \(\Delta = 3\), Discrete Math., 308, 4003-4007 (2008) · Zbl 1203.05052
[3] Coker, T.; Johannson, K., The adjacent vertex distinguishing total chromatic number, Discrete Math., 312, 2741-2750 (2012) · Zbl 1245.05042
[4] Huang, D.; Wang, W., Adjacent vertex distinguishing total colorings of planar graphs with large maximum degree, Sci. Sin. Math., 42, 151-164 (2012), (in Chinese) · Zbl 1488.05182
[5] Hulgan, J., Concise proofs for adjacent vertex-distinguishing total colorings, Discrete Math., 309, 2548-2550 (2009) · Zbl 1221.05143
[6] Vizing, V., Some unsolved problems in graph theory, Uspekhi Mat. Nauk, 23, 117-134 (1968), (in Russian) · Zbl 0177.52301
[7] Wang, H., On the adjacent vertex distinguishing total chromatic number of the graphs with \(\Delta(G) = 3\), J. Comb. Optim., 14, 87-109 (2007) · Zbl 1125.05043
[8] Zhang, Z.; Chen, X.; Li, J.; Yao, B.; Lu, X.; Wang, J., On adjacent-vertex-distinguishing total coloring of graphs, Sci. China Ser. A, 48, 289-299 (2005) · Zbl 1080.05036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.