大围长图的广义无圈染色

The Generalized Acyclic Chromatic Number of Graphs with Large Girth

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

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）△.