低度系列平行图的邻点可区别全染色  

作　　者：王淑栋[1] 任淑红[2] 

机构地区：[1]北京大学信息科学技术学院,北京100871 [2]山东科技大学信息科学与工程学院

出　　处：《自然科学进展》2007年第6期779-788,共10页

基　　金：国家自然科学基金资助项目(批准号:60503002)

摘　　要：设G是阶数不小于2的简单连通图,G的k-正常全染色σ称为是邻点可区别的,如果对G的任意两个相邻顶点,它们的顶点及关联边的颜色构成的集合不同.满足上述条件的最小k称为是G的邻点可区别全色数.文中从系列平行图的结构性质出发,利用换色技巧、归纳法以及组合方法对最大度不大于7的系列平行图的邻点可区别全染色进行了研究.得到了当低度系列平行图中不含相邻最大度点时,其邻点可区别全色数是最大度加1,否则,其邻点可区别全色数的上界为最大度加3.

关 键 词：系列平行图 邻点可区别全染色 邻点可区别全色数 

分 类 号：O157.5[理学—数学]