| 大围长图的广义无圈染色 |
| |
| 引用本文： | 蔡建生,王光辉,闫桂英.大围长图的广义无圈染色[J].数学学报,2013(1):27-30. |
| |
| 作者姓名： | 蔡建生 王光辉 闫桂英 |
| |
| 作者单位： | 潍坊学院数学与信息科学学院;山东大学数学学院;中国科学院数学与系统科学研究院 |
| |
| 基金项目： | 国家自然科学基金(11001055);山东省自然科学基金(ZR2009AM009,ZR2011AL008)资助项目 |
| |
| 摘 要： | 图的顶点染色称为是r-无圈的,如果它是正常染色,使得每一个圈C上顶点的颜色数至少为min{|C|,r}.图G的r-无圈染色数是图G的r-无圈染色中所用的最少的颜色数.我们证明了对于任意的r≥4,最大度为△、围长至少为2(r-1)△的图G的r-无圈染色数至多为6(r-1)△.
|
| 关 键 词： | 围长 染色 无圈染色 局部引理 |
The Generalized Acyclic Chromatic Number of Graphs with Large Girth |
| |
| Jian Sheng CAI,Guang Hui WANG,Gui Ying YAN.The Generalized Acyclic Chromatic Number of Graphs with Large Girth[J].Acta Mathematica Sinica,2013(1):27-30. |
| |
| Authors: | Jian Sheng CAI Guang Hui WANG Gui Ying YAN |
| |
| Institution: | 1 School of Mathematics and Information Sciences,Weifang University, Weifang 261061,P.R.China 2 School of Mathematics,Shandong University,Ji’nan 250100,P.R.China 3 Academy of Mathematics and System Science,Chineses Academy of Sciences, Beijing 100190,P.R.China |
| |
| Abstract: | A vertex coloring of a graph G is called r-acyclic if it is a proper vertex coloring such that every cycle C receives at least min{|C|,r} colors.The r-acyclic chromatic number of G is the least number of colors in an r-acyclic coloring of G.We prove that for any number r≥4,the r-acyclic chromatic number of any graph G with maximum degree△and with girth at least 2(r—1)△is at most 6(r—-1)△. |
| |
| Keywords: | girth coloring acyclic coloring local lemma |
| 本文献已被 CNKI 等数据库收录！ |
|
