Generalized Petersen graphs admit proper total colorings with four distinguishing constraints

YANG Chao; YAO Bing; WANG Hong-yu

Issue 6

Jan. 2014

Turn off MathJax

Article Contents

Article Navigation > Journal of East China Normal University (Natural Sciences) > 2013 > (6): 57-67

YANG Chao, YAO Bing, WANG Hong-yu. Generalized Petersen graphs admit proper total colorings with four distinguishing constraints[J]. Journal of East China Normal University (Natural Sciences), 2013, (6): 57-67.

Citation:

YANG Chao, YAO Bing, WANG Hong-yu. Generalized Petersen graphs admit proper total colorings with four distinguishing constraints[J]. Journal of East China Normal University (Natural Sciences), 2013, (6): 57-67.

Citation:

PDF( 330 KB)

Generalized Petersen graphs admit proper total colorings with four distinguishing constraints

1.
College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China

Received Date: 2012-11-01
Rev Recd Date: 2013-03-01
Publish Date: 2013-11-25

Abstract

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$.
- total coloring,
- vertex distinguishing total colorings,
- generalized Petersen graphs

FullText(HTML)

References(1)

References

[1]

{1} BURRIS A C, SCHELP R H. Vertex-distinguishing proper edge-coloring[J]. J Graph Theory, 1997, 26(2): 70-82.
{2} ZHANG Z F, LIU L Z, WANG J F. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002, {15(5)}: 623-626.
{3} VIZING V G. Some unsolved problems in graph theory[J]. Uspekhi Mat Nauk, {1968, 23: 117-134}.
{4} BEHZAD M. Graphs and their chromatic numbers[D]. Michigan: Michigan State University, 1965.
{5} ZHANG Z F, CHEN X E, LI J W, et al. On the adjacent vertex-distinguishing total coloring of graphs[J]. Science in China Series A.Mathematics(Chinese), 2004, {34(5)}: 574-583.
{6} BONDY J A, MURTY U S R. Graph Theory with Applications[M]. New York: Macmillan Press, 1976.
{7} WANG L W. On adjacent vertex distinguishing total coloring of generalized Petersen Graph[J]. ShanDong Science, 2007, {20(6)}: 4-8.

Relative Articles

Supplements(0)

Cited By

Proportional views