王 蓓 蓓，　祁 丽 娟，　刘 信 生，　陈 祥 恩

( 1.西北师范大学 数学与统计学院, 甘肃 兰州　730070；2.兰州工业学院 基础学科部, 甘肃 兰州　730050 )



完全二部图K5,7点强可区别全染色方案探讨

王 蓓 蓓1，祁 丽 娟*2，刘 信 生1，陈 祥 恩1

( 1.西北师范大学 数学与统计学院, 甘肃 兰州730070；2.兰州工业学院 基础学科部, 甘肃 兰州730050 )

摘要：利用组合分析的方法先讨论了完全二部图K5,7的点强可区别全染色，在此基础之上给出了两种具体的关于完全二部图K5,7的点强可区别全染色方案．此结果的给出不仅确定了完全二部图K5,7的点强可区别全色数为9，而且对于胡志涛所提出的关于完全二部图的点强可区别全染色的猜想：“如果m≥4且n<2m-2时，那么

χ

vst(Km,n)=n+3”中当m=5时作出了否定，从而进一步确定了此猜想成立的范围．

关键词：正常全染色；完全二部图；点强可区别全染色；点强可区别全色数

0引言

图染色的基本问题就是确定其各种染色法的色数．图的染色问题一直是图论研究的重要问题之一，具有重要的理论和实际意义．现实生活中的许多领域都会涉及图的着色，如任务分配问题、排课表问题、存储问题、交通定向问题等．所以染色问题一直是图论研究领域较为活跃的一部分．文献[1]中，Zhang等提出了邻点强可区别全染色的概念，并研究讨论了完全二部图的邻点强可区别全染色．在文献[2]中胡志涛等通过对图的邻点强可区别全染色的要求加强之后提出了图的点强可区别正常全染色，并研究了完全二部图K4,n(n>4)的点强可区别全染色；文献[3-4]研究了当1≤m≤3时的完全二部图Km,n(m≤n)的点强可区别全染色；文……