【摘要】 图的顶点染色称为是r-无圈的,如果它是正常染色,使得每一个圈C上顶点的颜色数至少为min{|C|,r}.图G的r-无圈染色数是图G的r-无圈染色中所用的最少的颜色数.我们证明了对于任意的r≥4,最大度为△、围长至少为2(r-1)△的图G的r-无圈染色数至多为6(r-1)△.更多还原

【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)△.更多还原