图的2-强点可区别全色数的上界  

An Upper Bound on the 2-Strongly Vertex-distinguishing Total Chromatic Number of Graphs

作　　者：贾泽乐 王鸿杰[1] 李沐春[1] JIA Zele;WANG Hongjie;LI Muchun(Institute of Applied Mathematics, Lanzhou Jiaotong University, Lanzhou Gansu 730070)

机构地区：[1]兰州交通大学应用数学研究所

出　　处：《首都师范大学学报（自然科学版）》2019年第4期5-8,共4页Journal of Capital Normal University：Natural Science Edition

基　　金：国家自然科学基金(11461038,61163010);甘肃省教育厅基金(2017A-021);兰州交通大学青年基金(2016014,2017004,2017021)资助项目

摘　　要：图的2-强点可区别全染色是满足2-距离以内的点可区别的正常全染色,其中色集合为点及其关联元素所染颜色构成的集合.图的2-强点可区别全色数是满足2-强点可区别全染色所用的最小颜色数.应用Lovász局部引理得到了图G的2-强点可区别全色数的上界.确切地,对不含孤立边的简单图G都有χ2-svdt(G)≤35d^2,其中d为G的最大度.A 2-strongly vertex-distinguishing total coloring of graphs is a proper total coloring such that no two vertices with distance no more than 2 have the same color set, where the color set of a vertex is a set consisted of the colors dyed on the vertex and its incident elements. A 2-strongly vertex-distinguishing total chromatic number is the minimum number required for a 2-strongly vertex-distinguishing total coloring of graphs. In this paper, by applying Lovász local lemma we obtain that, for any graph without isolated edges, the upper bound of 2-strongly vertex-distinguishing total chromatic number is at most 35d^2.

关 键 词：Lovász局部引理 2-强点可区别全染色 上界 

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