图的完全b-染色数的研究

On the complete b-chromatic number of a graph

通过将图的b-染色(数)概念的条件加强,提出图的完全b-染色(数)的概念.在b-染色问题中,染色只要求在每一个颜色类中都至少存在一个b-染色顶点,而在完全b-染色问题中,染色不但要满足上述条件,而且要求每一个顶点v,其顶点度大于等于G的完全b-染色数减1,且都是b-染色顶点.研究了路、圈、方形网格和满n叉树图的完全b-染色问题.对于路、圈、方形网格及满n叉树图,给出了染色方案,并求出了完全b-染色数.

A concept called the complete b-coloring（b-chromatic number） for vertices of graphs by strengthening the condition of the b-coloring（b-chromatic number） was proposed.In the problem of b-coloring,each color class has at least a b-coloring vertex.In the complete b-coloring,colorins not only must meet the above conditions,but also refer to each vertex v.The degree of vertex v is equal to or great than the complete b-chromatic number of graph G minus 1,and v is a b-coloring vertex.The problem of complete b-coloring of some graph is studied,such as paths,the circles,square grids and the full n-ary tree.The coloring schemes for paths,circles,square grids and the full n-ary tree are proposed,and the complete b-chromatic number of these graphs is obtained