没有K_4-图子式的图的邻点可区别全染色  

作　　者：王维凡[1] 王平 

机构地区：[1]浙江师范大学数学系,金华321004 [2]Department of Mathematics,Statistics and Computer Science,St.Francis Xavier University

出　　处：《中国科学（A辑）》2009年第12期1462-1472,共11页Science in China(Series A)

基　　金：国家自然科学基金(批准号:10771197);The James Chair at St.Francis Xavier University和Natural Sciencesand Engineering Research Council of Canada资助项目

摘　　要：图G的邻点可区别全染色是G的一个正常全染色,使得每一对相邻顶点有不同的颜色集合.G的邻点可区别全色数χa(G)是使得G有一个k-邻点可区别全染色的最小的整数k.本文完整刻画了没有K4-图子式的图的邻点可区别全色数.证明了:如果G是一个满足最大度△≥3且没有K4-图子式的图,则△+1≤χa(G)≤△+2,且χa(G)=△+2当且仅当G中含有两个相邻最大度点.

关 键 词：邻点可区别全染色 没有K4-图子式的图 最大度 

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