图的星色数的两个结果  

Two Results of the Star Chromatic Number of Graphs

作　　者：安明强[1] 

机构地区：[1]天津科技大学理学院,天津300457

出　　处：《天津科技大学学报》2010年第5期76-78,共3页Journal of Tianjin University of Science & Technology

基　　金：天津科技大学科学研究基金资助项目(20090222)

摘　　要：图G的星染色是图G的正常点染色,使得图G中没有长为3的路2-染色.通过应用概率方法中的非对称局部引理,证明了任一最大度为Δ的图的星色数χs(G)≤48Δ3.通过应用第一矩量原理和Markov不等式,证明了对任一有n个顶点的最大度为Δ的图G,其星色数χs(G)≤nΔ.A star coloring of a graph G is a proper coloring of G such that no path of length 3 in G is bicolored.It was proved that every graph with maximum degree Δ has a star coloring with at most 48Δ 3 colors by using the Asymmetric Local Lemma of probabilistic method.And It was also proved that every graph with n vertices and with maximum degree Δ has a star coloring with at most nΔ colors by using the First Moment Principle and Markov’s Inequality.

关 键 词：点染色 正常染色 星染色 星色数 概率方法 

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