An improved upper bound on the adjacent vertex distinguishing total chromatic number of graphs

Abstract

An adjacent vertex distinguishing total k-coloring of a graph G is a proper total k-coloring of G such that any pair of adjacent vertices have different sets of colors. The minimum number k needed for such a total coloring of G is denoted by χa′′(G). In this paper we prove that χa′′(G)≤2Δ(G)−1 if Δ(G)≥4, and χa′′(G)≤⌈[Formula presented]⌉ in general. This improves a result in Huang et al. (2012) which states that χa′′(G)≤2Δ(G) for any graph with Δ(G)≥3.