呂闖+張若東

[摘要]設(shè)圖G為b-染色圖，其b-染色數(shù)為φ（G）。圖G的b-染色數(shù)和為φ′（G）=min{V∈V（G）c（v）|c∈C}，其中c為圖G的任意一個(gè)[φ（G）]b-染色方案。通過構(gòu)造染色方案與染色和分解的方法，研究了扇圖F1，n與冠圖PnCn的b-染色數(shù)和。

[關(guān)鍵詞]冠圖；扇圖；m-度；b-染色；b-染色數(shù)；b-染色數(shù)和

2015年，Lisna在圖的b-染色[1]基礎(chǔ)上引入圖的“b-染色數(shù)和”[2]的概念。圖G的一個(gè)（k）b-染色是從頂點(diǎn)集V（G）={v1，v2，…，vn}到色數(shù)集c（G）={1，2，…，k}的一個(gè)滿映射c，且c為圖G的一個(gè)正常頂點(diǎn)染色V（G）=（V1，V2，…，Vk），即c（Vi）=i，且i，1≤i≤k，u∈Vi，使得j，1≤j≠i≤k，v∈Vj，有uv∈E（G），頂點(diǎn)u稱為b-支配頂點(diǎn)。圖G的b-染色數(shù)φ（G）=max{k|用k種顏色可以G進(jìn)行b-染色}。在參考文獻(xiàn)[3]、[4]、[5]、[6]中，人們對(duì)一些特殊圖類的b-染色數(shù)進(jìn)行了研究，得出很多重要結(jié)論。在參考文獻(xiàn)[2]中，Lisna研究一些圖類的b-染色數(shù)和，且闡述了b-染色數(shù)和理論在交通網(wǎng)絡(luò)應(yīng)用問題中的應(yīng)用的優(yōu)點(diǎn)。本文通過構(gòu)造染色方案與染色和分解的方法，研究得出了扇圖F1，n與冠圖PnCn的b-染色數(shù)和。

1主要結(jié)論

定理1設(shè)F1，n為n+1階扇圖，其中n≥2，則F1，n為可b-染色圖，且

（1）當(dāng)2≤n≤4時(shí)，因m（F1，n）=3，且用3種顏色可對(duì)F1，n進(jìn)行b-染色，具體見染色方案1。根據(jù)引理1，所以φ（F1，n）=3。在染色方案1中，最大顏色3只用了1次，而顏色1用得最多，即該染色方案恰好使得染色數(shù)和達(dá)到最小，所以有如下結(jié)論成立。

2結(jié)論

本文冠圖PnCn及扇圖F1，n的b-染色數(shù)和，其思想方法對(duì)于其他一般圖的b-染色數(shù)和的確有一定的借鑒意義，確定圖的b-染色數(shù)是NP-難問題，根據(jù)“b-染色數(shù)和”的定義確定b-染色數(shù)將會(huì)更加困難，這些問題都有待研究，且有研究價(jià)值。

參考文獻(xiàn)：

[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—），男，吉林吉林人，講師。