关于图的模染色数的上界

On the Upper Bound of Modular Chromatic Number of Graphs

图的模染色是由邻点赋权导出的一种染色,是图的经典染色的一种推广。本文主要运用概率方法中的Lovasz局部引理,较大幅度地改进了关于图的模染色数的上界。

The modular coloring of a graph is induced by the weights of neighboring vertices. It is a generalization of the classic graph coloring. In this paper, we obtain a general upper bound for the modular chromatic number of graphs by using the Lovasz Local Lemma. Our result improves previous exponential bound significantly.