马宝林,刘娟,王军涛,丁玉荣

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

关于路的并的点可区别V-全染色

马宝林,刘娟,王军涛,丁玉荣

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

根据简单图的点可区别V-全染色的概念及其染色方法,讨论了m个长度为n的路的顶点不交并的点可区别V-全染色,并给出全色数的结论及其证明,根据结论提出了相应的猜想,为进一步探讨其他简单图的点可区别V-全染色提供了理论证据,丰富了图的点可区别V-全染色的结果.

简单图；全色数；点可区别V-全染色；mPn

图的染色问题是NP完全问题,目前已得到了很多结果[1-3],2004年,张忠辅、陈祥恩等在图的全染色的基础上提出了邻点可区别全染色[1],2008年,又在点可区别正常全染色的基础上提出了图的点可区别一般全染色[2].本文从简单图的点可区别V-全染色的定义出发,讨论mP2、mP3、mP4的点可区别V-全染色,给出全色数的结论及其证明,并提出了自己的猜想.

1 相关概念

在文献[1]和[2]中,对于部分简单图的点可区别正常全染色已有相对完善的结果,并给出定义,图的正常全染色是指：（1）相邻的两个顶点染色不同；（2）相邻的两条边染色不同；（3）任意的点和与之关联的边染色不同,并用χvt(G)表示了图的点可区别全色数.如若上述（1）～（3）条件中只满足其中一个或两个条件时就被称之为图的一般全染色.本文仅考虑只满足（2）和（3）时的情形.

定义设G是一个简单图,k是正整数,f是V( G)∪E( G)到{1,2,3,…,k}的一个映射,对图G的一个全染色f,用C( u)表示点u和它所关联的边所染的颜色组成的……