On the adjacent vertex-distinguishing total colorings of some cubic graphs

Abstract

Suppose $G=(V,E)$ is a simple graph and $f:(V\cup E)\to 1,2,\dots ,k$ is a proper total k-coloring of G. Let $C(u)=f(u)\cup f(uv):uv\in E(G)$ for each vertex u of G. The coloring f is said to be an adjacent vertex-distinguishing total coloring of G if $C(u)\ne C(v)$ for every $uv\in E(G)$. The minimum k for which such a chromatic number of G, and is denoted by $X_{a}t(G)$. This paper considers three types of cubic graphs: a specific family of cubic hasmiltonian graphs, snares and Generalized Petersen graphs. We prove that these cubic graphs have the same adjacent vertex-distinguishing total chromatic number 5. This is a step towards a problem that whether the bound $X_{a}t(G)\le 6$ is sharp for a graph G with maximum degree three.