Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree
Weifan Wang, Danjun Huang · Scientia Sinica Mathematica · 2012
An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors needed for an adjacent vertex distinguishing total coloring of G is denoted by χa′′(G). In this paper, we prove that every planar graph G with Δ(G) ≥ 11 has χa′′(G) ≤ Δ(G) + 3.