r-条件染色正常图的两个充分条件

TWO SUFFICIENT CONDITIONS OF NORMAL GRAPHS IN r-CONDITIONAL COLORING

对整数r＞0，图G的一个r-条件染色是一个从顶点集V（G）到数集｛1，2，…，k｝的映射c，使得：1）相邻点获得的颜色不同；2）｜c（N（v））｜≥min ｛｜N（v）｜，r｝。（其中N（v）代表v的邻点集）。使图G有一个正常的（k，r）-染色的最小k值称为G的条件色数。若图G的r-条件色数等于G的色数，则称图G为r-正常的。笔者给出了判断一个图为r-正常图的两个充分条件。

For a positive integer r,a r-conditional coloring of a graph G is a map c：V（G）→{1 ,2,…,k}, such that：1 ）if u,v∈V（G）are adjacent vertices in G,then c（u）≠c（v）;2）for any u∈V（G）,｜c（N（v））｜≥min{｜N（v）｜,r}.（N（v）is the set of vertices which are adjacent to vertex v）.The r-coloring chromatic number of G is the smallest k such that G has a proper（k,r）-coloring.A graph G is r-normal provided that the r-conditional chromatic number of G equals the chromatic number of G.Two conditions which are sufficient for a graph to be r-normal are given.