图的星色数的两个结果

Two Results of the Star Chromatic Number of Graphs

图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.