圈的三种积图的b-染色与b-边染色

The b-coloring and b-edge Coloring of Product Graphs of Cycles

设σ是G的一个k-点染色,若在G中一定存在一个点,使得该点在其他k-1个色类中都至少有一个邻居,则称该点为b-点,称σ为G的一个b-染色.其中,最大的k值称为G的b-色数,记为φ(G).设σ是G的一个k-边染色,若在G中一定存在一条边,使得该边在其他k-1个色类中都至少有一个邻居,则称该边为b-边,称σ为G的一个b-边染色.其中,最大的k值称为G的b-边色数,记为φ'(G).

Letσbe a proper k-coloring of the vertices of graph G,and if there must be a vertex in G that has at least one neighbor in other k-1 color classes,then that point is called a b-vertex and the coloringσis called a b-coloring of G,where the greatest integer k is the b-chromatic number of G,denotedφ(G).Letσbe a proper k-edge coloring of G,and if there must be a edge in G that has at least one neighbor in other k-1 color classes,then that edge is called a b-edge and the coloringσis called a b-edge coloring of G,where the greatest integer k is the b-chromatic index of G,denotedφ'(G).In this article,we have studied the three types of product graph in two cycles:Cartesian product,direct product and strong product with b-chromatic number and b-chromatic index.