杨 青, 田双亮, 索郎王青

(西北民族大学 数学与计算机科学学院, 兰州 730030)

1 引言与预备知识

在图染色中, 通常研究图元素的最小分类问题.但还有一类染色研究图元素的最大分类问题, 如b-染色[1]与Achromatic-染色[2]等.b-染色是在Achromatic-染色基础上提出的染色概念, 关于b-染色的研究目前已有很多结果[3-10]: Vivin等[3]研究了任意两个图的冠积可b-染色, 并给出了任意图与其同阶路、圈、完全图的冠积b-色数; 在文献[3]的基础上, 代天骄等[4]研究了路、圈与完全图的冠积的m-度与b-色数; 吕闯等[5-6]研究了路、圈、轮等所构成的冠积的m-度与b-色数.关于图的广义冠积和广义边冠积的研究可参见文献[11-12].本文主要研究图的冠积和边冠积的b-色数, 并在此基础上推出广义(边)冠积的b-色数.

本文讨论的图均为简单图, 分别用V(G),E(G),Δ(G),δ(G)表示图G的顶点集、边集、最大度和最小度, 用dG(v)表示G中顶点v的度数,Nr(v)表示顶点v相邻的r个顶点的集合, 其中r≤dG(v).设σ为G的一个k-正常染色, 用S(A)表示A中顶点颜色的集合,Si(G)表示G中颜色为i的所有顶点的集合, 其中A⊆V(G)且i∈{1,2,…,k}.记[n]={1,2,…,n}.本文未说明的符号及术语可参见文献[13].

定义1[1]设{V1,V2,…,Vk}为图G的一个k-正常点染色, 若对任意的i∈{1,2,…,k}, 存在b-点ν∈vi, 使得{v}∪Vj为非独立集, 其中j=1,2，…，k且j≠i, 则称该点染色为图G的一个k-b-染色, 最大的k值为图G的b-色数, 并记为φ(G).

定义2[1]设图G的顶点集为V(G)={v1,v2,…,vn}且

dG(v1)≥dG(v2)≥…≥dG(vn),

称m(G)=max{1≤i≤n,dG(vi)≥i-1}为图G的m-度.

根据上述定义, 显然有如下结果:

引理1对任意图G, 有

χ(G)≤φ(G)≤min{Δ(G)+1,m(G)}=m(G).

对任意两个图G与H, 设V(G)={v1,v2,…,vn},E(G)={e1,e2,…,ek}, 若对H有n次拷贝, 将第i次拷贝的Hi所有顶点与G中顶点vi连接, 其中i∈[n], 这样构造的图称为G与H的冠积[14], 记为G∘H.若H有k次拷贝……