Upper bounds on adjacent vertex distinguishing total chromatic number of graphs

Abstract An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that for any pair of adjacent vertices, the set of colors appearing on the vertex and incident edges are different. The minimum number of colors required for an adjacent vertex distinguishing total coloring of G is denoted by χ a ′ ′ ( G ) . Let G be a graph, and χ ( G ) and χ ′ ( G ) be the chromatic number and edge chromatic number of G , respectively. In this paper we show that χ a ′ ′ ( G ) ≤ χ ( G ) + χ ′ ( G ) − 1 for any graph G with χ ( G ) ≥ 6 , and χ a ′ ′ ( G ) ≤ χ ( G ) + Δ ( G ) for any graph G . Our results improve the only known upper bound 2 Δ obtained by Huang et al. (2012). As a direct consequence, we have χ a ′ ′ ( G ) ≤ Δ ( G ) + 3 if χ ( G ) = 3 and thus it implies the known results on graphs with maximum degree 3, K 4 -minor-free graphs, outerplanar graphs, graphs with maximum average degree less than 3, planar graphs with girth at least 4 and 2-degenerate graphs.