Journal of East China Normal University(Natural Sc ›› 2013, Vol. 2013 ›› Issue (6): 57-67.

• Article • Previous Articles     Next Articles

Generalized Petersen graphs admit proper total colorings with four distinguishing constraints

YANG Chao, YAO Bing, WANG Hong-yu   

  1. College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China
  • Received:2012-11-01 Revised:2013-03-01 Online:2013-11-25 Published:2014-01-13

Abstract: The study of distinguishing coloring in graphs is derived
from the frequency assignment problem in mobile communications. This
paper introduced the concept of $4$-adjacent vertex distinguishing
total coloring ($4$-avdtc) of a simple graph $G$. The minimum number
of $k$ colors required for $G$ such that it satisfies a $4$-avdtc is
denoted as $\chi^{\prime\prime}_{4as}(G)$. For generalized Petersen
graphs $P(n,k)$, it was proved that $6\leq
\chi^{\prime\prime}_{4as}(P(n,k))\leq 7$.

Key words: total coloring, vertex distinguishing total colorings, generalized Petersen graphs

CLC Number: