Adjacent Vertex Distinguishing Total Colorings of Outer 1-Planar Graphs

Abstract

An adjacent vertex distinguishing total coloring of a graph $G$ is a proper total coloring of $G$ such that no pair of adjacent vertices are incident to the same set of colors. The minimum number of colors required for an adjacent vertex distinguishing total coloring of $G$ is denoted by $\chi {”}_a(G)$. In this paper, we prove that if $G$ is an outer 1-planar graph with at least two vertices, then $\chi {”}_a(G)\le max\{\mathrm{\Delta }+2,8\}$. Moreover, we also prove that when $\mathrm{\Delta }\ge 7$, $\chi {”}_a(G)=\mathrm{\Delta }+2$ if and only if $G$ contains two adjacent vertices of maximum degree.