Hits :

First Author : 王维凡

Affiliation of Author(s): 数理与信息工程学院

Date of Publication : 2009-01-01

Document Type : 期刊

Journal : 中国科学(A辑:数学)

Issue : 第12期

Page Number : 1462-1472

ISSN : 1674-7216

Translation or Not : no

Key Words : 邻点可区别全染色；没有K4-图子式的图；最大度

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