广义Petersen图的2-hued着色

2-hued Coloring of the Generalized Petersen Graph

设正整数k,r>0,图G的一个(k,r)-着色是用k种颜色对顶点集V(G)进行正常着色,使得对任意v∈V(G),至少连接min{d_(G)(v),r}种不同颜色的顶点.图G的r-hued着色数,记为χ_(r)(G),是使得图G具有(k,r)-着色的最小正整数k.已知广义Petersen图的2-hued着色数是3或4,分别刻画2-hued着色数为3或4的广义Petersen图.

For integers k,r>0,a(k,r)-coloring is a proper coloring on the vertex set V(G)by k colors,such that each vertex v is adjacent to vertices with at least min{d_(G)(v),r}different colors.The r-hued chromatic number of a graph G,denoted byχ_(r)(G),is the smallest integer k for which the graph G has a(k,r)-coloring.The 2-hued chromatic number of the generalized Petersen graph is 3 or 4.In this paper,we characterize generalized Petersen graphs with 2-hued chromatic number 3 or 4,respectively.