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

Huang, Danjun; Wang, Weifan; Yan, Chengchao

Discrete Math. 312, No. 24, 3544-3546 (2012).

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)\).

Reviewer: Marcin Anholcer (Poznan)

MSC:

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

Keywords:

adjacent vertex distinguishing total coloring; total coloring; coloring; total chromatic number; adjacent vertex distinguishing total chromatic number

Citations:

Zbl 1080.05036; Zbl 1203.05052; Zbl 1221.05143; Zbl 1125.05043; Zbl 1245.05042

References:

[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