平面图的邻点可区别全染色  

Adjacent-vertex-distinguishing total coloring of planar bipartite graphs

作　　者：李泽鹏[1] 王治文[2] 陈祥恩[1] 

机构地区：[1]西北师范大学数学与信息科学学院,甘肃兰州730070 [2]宁夏大学数学计算机学院,宁夏银川750021

出　　处：《山东大学学报（理学版）》2011年第4期4-8,16,共6页Journal of Shandong University(Natural Science)

基　　金：国家自然科学基金资助项目(10771091);宁夏大学科学研究基金((E):ndzr10-7)

摘　　要：图G的一个正常全染色f称为是邻点可区别的,如果G中任何相邻点的点及其关联边的颜色集合不同。对一个图G进行邻点可区别的正常全染色所用最少颜色数称为G的邻点可区别全色数,记为χat(G)。证明了χat(G)≤Δ(G)+2对任意的Δ(G)≥11且围长至少为4的平面图G成立。A proper total coloring of G is an adjacent vertex distinguishing total coloring if for any two adjacent vertices,the sets of colors appearing on the vertex and incident edges are different.The smallest number of colors of which such a coloring of G exists is called the adjacent vertex distinguishing total chromatic number,and is denoted by χat（G）.It is proved that χat（G）≤Δ（G）＋2 for any planar bipartite graph G with maximum degree Δ（G） at least 11 and girth at least 4.

关 键 词：图 平面图 邻点可区别全染色 邻点可区别全色数 

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