条件染色正常图的几个充分条件

Several sufficient conditions of a normal graph in conditional coloring

给定正整数r,图G的一个r-条件染色是G的顶点的一个正常染色,使得G中任意度数为d(v)的顶点v,其邻域中至少出现min{r,d(v)}种不同的颜色。若图的r-条件色数等于色数,则称图为r-正常的。给出了判断一个图G为正常图的一些充分条件,并用实例说明了这些条件并非必要的。

For positive integer r, a r-conditional coloring of a graph G is a proper vertex coloring of G such that every vertex v of degree d（v） in G is adjacent to vertices with at least min {r, d（v） } different colors. A graph G is r-normal, if the r-conditional chromatic number of G equals the chromatic number of G. The conditions, which are sufficient for a graph to be normal, are given. Some examples are given to illustrate the conditions are not necessary.