点击量 ：

第一作者 ： 王维凡

发表时间 ： 2009-01-01

发表刊物 ： 中国科学(A辑:数学)

所属单位 ： 数理与信息工程学院

文献类型 ： 期刊

期号 ： 第12期

页面范围 ： 1462-1472

ISSN ： 1674-7216

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

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

是否译文 ： 否