论文部分内容阅读
对整数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-正常图的两个充分条件。