On Adjacent Vertex-Distinguishing Total Chromatic Number of Generalized Petersen Graphs

摘要

Analyzing chromatic number in coloring problem is a tough topic in graph analysis. We focus on the basic theory for a particular type of chromatic number. This will give us insights on the basic topological structure guiding lots of networks in the coming trend of big data era. An adjacent vertex-distinguishing total k-coloring is a proper total k-coloring of a graph G such that for any two adjacent vertices, the set of colors appearing on the vertex and its incident edges are different. The smallest k for which such a coloring of G exists is called the adjacent vertex-distinguishing total chromatic number, and denoted by χat(G). It has been proved that if the graph G satisfies Δ(G)=3, then χat(G) ≤ 6. However, it is very difficult to determine whether χat(G) ≤ 5. In this paper, we focus on a special class of 3-regular graphs, the generalized Petersen graphs P(n, k), and show that χat(P(n, k)) = 5, which improves the bound χat(P(n, k)) ≤ 6.