若干个C3并的点可区别V-全染色

马宝林,张振亮,姚瑞

（河南科技学院,河南新乡453003）

若干个C3并的点可区别V-全染色

马宝林,张振亮,姚瑞

（河南科技学院,河南新乡453003）

根据简单图的点可区别V-全染色的概念及其染色方法,讨论若干个阶为3的圈的顶点不交并的点可区别V-全染色,并给出其全色数及染色方案,为进一步探讨mCn的点可区别V-全染色提供了理论证据,丰富了图的点可区别V-全染色的结果.

简单图；全色数；点可区别V-全染色；圈的顶点不交并

张忠辅、陈祥恩等于2004年在图的全染色概念的基础上提出了邻点可区别全染色概念[1],2008年,他们又在点可区别正常全染色的基础上提出了图的点可区别一般全染色[2].本文将从简单图的点可区别V-全染色的定义出发,讨论mC3的点可区别V-全染色并给出其全色数及证明．

1 相关概念

文献[1]和[2]中给出了简单图的点可区别正常全染色的研究,并用表示图的点可区别全色数.

定义1设G为一个阶不小于2的简单连通图,k是一个正整数,A：{1,2,…,k}为一个色集合,如果以下3个条件被满足：（v）对uv∈E（G）,有f( u)≠f( v)；（e）对uv,vw∈E（G）,u≠w,有f( uv)≠f( vw)；（i）对uv∈E（G）,有f( u)≠f( v)≠f( uv ).则f称为G的正常全染色．

上述条件中,若只满足其中一个或两个条件时就被称之为图的一般全染色.本文仅考虑只满足（e）和（i）时的情形.

定义2设G是一个简单图,k是正整数,f是一个从V（G）∪E（G）到集合{1,2,…,k}的映射,对图G的一个全染,用C（u）表示点u和它所关联的边所染的颜色组成的集合.若对于G的任意两点u和v,都有C（u）≠C（v）,则称是图G的点可区别V-全染色,简称为图G的VDVT染色.

图G的一个VDVT染色所需要的最少颜色的……