关键词: 条件染色;条件色数;正常图

Abstract:

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.

Key words: conditional coloring; conditional chromatic number; normal graph