两类图的b—染色数和研究

吕闯+张若东

[摘要]设图G为b-染色图，其b-染色数为φ（G）。图G的b-染色数和为φ′（G）=min{V∈V（G）c（v）|c∈C}，其中c为图G的任意一个[φ（G）]b-染色方案。通过构造染色方案与染色和分解的方法，研究了扇图F1，n与冠图PnCn的b-染色数和。

[关键词]冠图；扇图；m-度；b-染色；b-染色数；b-染色数和

2015年，Lisna在图的b-染色[1]基础上引入图的“b-染色数和”[2]的概念。图G的一个（k）b-染色是从顶点集V（G）={v1，v2，…，vn}到色数集c（G）={1，2，…，k}的一个满映射c，且c为图G的一个正常顶点染色V（G）=（V1，V2，…，Vk），即c（Vi）=i，且i，1≤i≤k，u∈Vi，使得j，1≤j≠i≤k，v∈Vj，有uv∈E（G），顶点u称为b-支配顶点。图G的b-染色数φ（G）=max{k|用k种颜色可以G进行b-染色}。在参考文献[3]、[4]、[5]、[6]中，人们对一些特殊图类的b-染色数进行了研究，得出很多重要结论。在参考文献[2]中，Lisna研究一些图类的b-染色数和，且阐述了b-染色数和理论在交通网络应用问题中的应用的优点。本文通过构造染色方案与染色和分解的方法，研究得出了扇圖F1，n与冠图PnCn的b-染色数和。

1主要结论

定理1设F1，n为n+1阶扇图，其中n≥2，则F1，n为可b-染色图，且

（1）当2≤n≤4时，因m（F1，n）=3，且用3种颜色可对F1，n进行b-染色，具体见染色方案1。根据引理1，所以φ（F1，n）=3。在染色方案1中，最大颜色3只用了1次，而颜色1用得最多，即该染色方案恰好使得染色数和达到最小，所以有如下结论成立。

2结论

本文冠图PnCn及扇图F1，n的b-染色数和，其思想方法对于其他一般图的b-染色数和的确有一定的借鉴意义，确定图的b-染色数是NP-难问题，根据“b-染色数和”的定义确定b-染色数将会更加困难，这些问题都有待研究，且有研究价值。

参考文献：

[1]Irving R W，Manlove D FThe b-chromatic Number of Graphs [J].Discrete Applied Mathematics，1999，91（1-3）： 127-141

[2]Lisna P C，Sunittha M SB-chromatic Sum of a Graph [J].Discrete Mathematics，Algorithms and Applications，2015，7（4）：1-15

[3]Balakrishnan R，Raj S F，Kavaskar TB-chromatic Number of Cartesian Product of Some Families of Graphs[J].Graphs and Combinatorics，2014（30）：511–520

[4]Campos V A，Lima C VThe b-chromatic Index of Graphs[J].Discrete Mathematics，2015（338）： 2072–2079

[5]Eschouf N I，Blidia M，Maffray FOn Edge-b-critical Graphs[J].Discrete Applied Mathematics，2015（180）：176-180

[6]Vivin J V，Venkatachalam MOn b-chromatic Number of Sun Let Graph and Wheel Graph Families[J].Journal of the Egyptian Mathematical Society，2015（23）：215-218

[7]Vivin J V，Venkatachalam MThe b-chromatic Number of Corona Graphs[J].Utilitas Mathematica，2012（88）：299-307

[作者简介]〖HT6SS〗吕闯（1980—），男，吉林吉林人，讲师。