Adjacent vertex distinguishing total coloring of graphs with maximum degree 4

Let kk be a positive integer. An adjacent vertex distinguishing (for short, AVD) totalkk-coloring ϕϕ of a graph GG is a proper total kk-coloring of GG such that no pair of adjacent vertices have the same set of colors, where the set of colors at a vertex vv is {ϕ(v)}∪{ϕ(e):e is incident to v}{ϕ(v)}∪{ϕ(e):e is incident to v}. Zhang et al. conjectured in 2005 that every graph with maximum degree ΔΔ has an AVD total (Δ+3)(Δ+3)-coloring. Recently, Papaioannou and Raftopoulou confirmed the conjecture for 44-regular graphs. In this paper, by applying the Combinatorial Nullstellensatz, we verify the conjecture for all graphs with maximum degree 4.