| 图的星色数的两个结果 |
| |
| 引用本文： | 安明强.图的星色数的两个结果[J].天津轻工业学院学报,2010(5):76-78. |
| |
| 作者姓名： | 安明强 |
| |
| 作者单位： | 天津科技大学理学院,天津300457 |
| |
| 基金项目： | 天津科技大学科学研究基金资助项目（20090222） |
| |
| 摘 要： | 图G的星染色是图G的正常点染色,使得图G中没有长为3的路2-染色.通过应用概率方法中的非对称局部引理,证明了任一最大度为Δ的图的星色数χs（G）≤48Δ3.通过应用第一矩量原理和Markov不等式,证明了对任一有n个顶点的最大度为Δ的图G,其星色数χs（G）≤nΔ.
|
| 关 键 词： | 点染色 正常染色 星染色 星色数 概率方法 |
Two Results of the Star Chromatic Number of Graphs |
| |
| AN Ming-qiang.Two Results of the Star Chromatic Number of Graphs[J].Journal of Tianjin University of Light Industry,2010(5):76-78. |
| |
| Authors: | AN Ming-qiang |
| |
| Affiliation: | AN Ming-qiang(College of Science,Tianjin University of Science ＆ Technology,Tianjin 300457,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | vertex coloring proper coloring star coloring star chromatic number probabilistic method |
| 本文献已被 维普 等数据库收录！ |
