图的星边星-全色数的一个上界  

An upper bound of star-edge-star total chromatic number of graphs

作　　者：刘信生[1] 孙春虎[1] 王志强[1] 

机构地区：[1]西北师范大学数学与信息科学学院,甘肃兰州730070

出　　处：《兰州理工大学学报》2012年第1期129-135,共7页Journal of Lanzhou University of Technology

基　　金：国家自然科学基金(61163054;61163037);甘肃省教育厅基金(0501-03)

摘　　要：提出图的星边星-全染色的概念,图G的一个正常全染色被称为星边星-全染色,如果对G中点进行星染色,边进行星边染色.并定义图的星边星-全色数,记为χsTs(G).用构造染色的方法给出一些特殊图(路,圈,轮,扇,完全图)的星边星-全色数.同时运用概率方法给出满足一定条件的图G的星边星-全色数的一个上界,即若图G的最大度Δ(G)≥30,则χsTs(G)≤24(Δ-1)3/2.A concept of star-edge-star total coloring of graphs was presented.A proper total coloring of a graph G would be called star-edge-star total coloring if its vertices were star coloring and its edges were star-edge coloring.The star-edge-star total chromatic number of G was defined and denoted by χTss（G）.The star-edge-star total chromatic number of some particular graphs（path,cycle,wheel,fan,complete graph） were given by using the method of coloring construction.Meantime,an upper bound of star-edge-star total chromatic number of graph which satisfied definite conditions,was given by means of probabilistic method,namely χTss（G）≤24（Δ-1）3/2 for a graph G if its maximum degree Δ（G）≥30.

关 键 词：星边星-全染色 星边星-全色数 概率方法 Lovász局部引理 

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