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

摘要

Suppose G - (V, E) is a simple graph and / : (V ∪ E) -¥ {1,2,... ,k} is a proper total fc-coloring of G. Let C(u) = {/(u)} ∪ {f(uv) : uv ∈ E(G)} for each vertex u of G. The coloring / is said to be an adjacent vertex-distinguishing total coloring of G if C(u) C(v) for every uv ∈ E(G). The minimum fc for which such a coloring of G exists is called the adjacent vertex-distinguishing total chromatic number of G, and is denoted by X_(at)(G). This paper considers three types of cubic graphs: a specific family of cubic hamiltonian 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_(at)(G) < 6 is sharp for a graph G with maximum degree three.