图的邻点可区别全染色的渐近性质  

Asymptotic Behavior of the Adjacent Vertex Distinguishing Total Coloring of Graphs

作　　者：晁福刚[1] 强会英[2] 盛秀艳[3] 

机构地区：[1]华东师范大学数学系,上海200241 [2]兰州交通大学应用数学研究所,甘肃兰州730070 [3]聊城大学数学科学学院,山东聊城252059

出　　处：《数学的实践与认识》2014年第1期147-150,共4页Mathematics in Practice and Theory

基　　金：国家自然科学基金(11171114)

摘　　要：图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同,其所用的最少颜色数称为邻点可区别全色数.张忠辅老师猜想:对于|V(G)|≥3的连通图G,其邻点可区别全色数最多不超过△(G)+3.用概率方法证明了对简单图G,△≥14,有χ_(at)(G)≤△+C,其中C≥10^(26)+1.A proper k-total coloring is called adjacent vertex distinguishing total coloring if any two adjacent vertices have different color sets. The least number of colours required for a adjacent vertex distinguishing total coloring is called adjacent vertex distinguishing total chromatic number. Zhang conjectured that, for connected graph, the adjacent vertex distinguishing total chromatic number is at most △（G）＋3. In this paper, using the probablistic methods, we prove that for any simple graph G, △ ≥14, then Xat（G） ≤△ ＋ C, where C ≥10^26 ＋ 1.

关 键 词：邻点可区别全染色 邻点可区别全色数 Lovász局部引理 

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