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

摘要

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 chi(a)"(G). In this paper we prove that chi(a)"(G) = 2 Delta(G) - 1 if Delta(G) = 4, and chi(a)"(G) = Inverted Right Perpendicular 5 Delta(G)+8/3 Inverted Left Perpendicular in general. This improves a result in Huang et al. (2012) which states that chi(a)"(G) = 2 Delta(G) for any graph with Delta(G) = 3. (C) 2017 Elsevier B.V. All rights reserved.