若干圖的冠積的星染色

蔡瑾 田雙亮 安卓莫

【摘要】 ?圖G的一個(gè)k-星染色σ是使G不存在4階的2色路的k-點(diǎn)染色， 其中最小的k值稱為G的星色數(shù)， 記為Xs（G）。 簡單圖G與H的冠積G·H被定義為將G的第i個(gè)頂點(diǎn)與第i個(gè)H的拷貝中每一個(gè)頂點(diǎn)連接得到的圖. 主要研究了任意圖G與H的冠積的星色數(shù)的上界及某些特殊圖G與任意圖H的冠積的星色數(shù)Xs（G·H）， 具體結(jié)果為：Xs（G·H）≤Xs（G）+Xs（H） ; 當(dāng)G為m階路時(shí)， Xs（Pm·H）=Xs（H）+2; 當(dāng)G為m+1解星時(shí)， Xs（K1，m·H）=Xs（H）+2; 當(dāng)G為m≠5階圈時(shí)，Xs（Cm·H）=Xs（H）+2 。

【關(guān)鍵詞】冠積 ?星染色 ?路 ?星 ?圈

一、引言

本文所考慮的圖都是有限無向的簡單連通圖，記（m）n=m（modn）， 其中m為整數(shù)，n為整數(shù)。

圖的點(diǎn)染色是圖論中的重要內(nèi)容，圖的正常點(diǎn)染色僅要求任意兩個(gè)相鄰的頂點(diǎn)所染的顏色不同，對(duì)點(diǎn)染色的要求不同，就會(huì)有不同的染色形式. 隨著對(duì)點(diǎn)染色的染色形式的廣泛推廣，提出了許多有意義的染色形式。圖G的一個(gè)k-星染色σ是使G中不存在4階的2色路的k-點(diǎn)染色， 其中最小的k值稱為G的星色數(shù)，記為Xs（G）， 該染色是由Grünbaum在文獻(xiàn)[1]中提出來的. 這種染色方式在許多文章中被研究，如Vinve在文獻(xiàn)[2]中推廣了圖的染色問題并以另一種形式引入了星染色的概念; Fertin等人在文獻(xiàn)[3]中確定了特殊圖的星色數(shù)的精確值以及部分圖的星色數(shù)的界; Albertson等人在文獻(xiàn)[4]中證明了平面圖的星色數(shù)最多不超過20; Lyons在文獻(xiàn)[5]中證明了圖的無圈染色也是一個(gè)星染色，且給出了一個(gè)尋找圖的最優(yōu)星染色的線性算法。

在下文的討論中將用到如下引理1.1-1.3。

引理1.1 對(duì)于任意整數(shù)n≥3，當(dāng)n≠5時(shí)，Xs（Cn）=3， 否則Xs（Cn）=4。

引理1.2 對(duì)于任意整數(shù)n，m≥2，Xs（Kn，m）=min{m，n}+1。

引理1.3 對(duì)于任意整數(shù)m≥3，Xs（Km）=m。

圖的運(yùn)算是研究圖的構(gòu)造的重要工具，其運(yùn)算方式有許多， 常見的圖的運(yùn)算有冠積、直積、強(qiáng)積、半強(qiáng)積等，其中m階圖G和n階圖H的冠積G·H被定義為取G的1個(gè)拷貝， H的m個(gè)拷貝，并將G的第i個(gè)頂點(diǎn)與第i個(gè)H的每一個(gè)頂點(diǎn)連接得到的圖， 這種運(yùn)算方式是由Harary和Frucht于1970年在文獻(xiàn)[6]中提出的。對(duì)于圖的冠積運(yùn)算研究有許多， 文獻(xiàn)[7-13]都對(duì)不同圖的冠積運(yùn)算的性質(zhì)進(jìn)行了研究. 本文將對(duì)特殊圖與任意圖的冠積的星染色進(jìn)行研究。

Venkatesan在文獻(xiàn)[14]中分別給出了n階路與n階完全圖， 階圈，n+1階星， n1+n2階完+1全二部圖及n=階星與n階完全圖的星色數(shù)，其主要研究結(jié)果如下：

命題1.1 對(duì)于任意n≥2，Xs（Pn·Kn）=n+2.n

命題1.2 對(duì)于任意n≥3， 若n=5則Xs（Pn·Cn）=6; 否則，Xs（Pn·Cn）=5。

命題1.3 對(duì)于任意正整數(shù)n≥3，Xs（Pn·K1，n）=4。

命題1.4 對(duì)于任意n≥2且n=n1或n=n2，Xs（Pn·Kn1，n2）=min{n1+n2}+3。

命題1.5 對(duì)于任意n≥3，Xs（K1，n·Kn）=n+2。

文獻(xiàn)[14]主要研究同階特殊圖的冠積的星色數(shù)，本文對(duì)其結(jié)果進(jìn)行推廣，分別得到了m階路以及m+1階星與任意簡單圖的星色數(shù).同時(shí)又研究了m階圈與任意簡單圖的星色數(shù)，并給出了對(duì)應(yīng)的染色方法.

二、主要結(jié)果及其證明

設(shè)G和H是階數(shù)分別為m，n的圖，其中m，n≥2， 且Xs（H）=r。記G，H和G·H中H的每一個(gè)拷貝Hi的頂點(diǎn)集分別為V（G）={x0，x1，…，xm-1}，V（H）={y0，y1，…，yn-1}，V（Hi）={y■■，y■■，…，y■■}，其中i=0，1，…，m-1。令H■■=K■■∨H■，其中V（H■■）={xi}∪V（Hi），V（K■■）={xi}，則G·H的邊集為E（G·H）=E（G）∪（∪■■E（H■■））。文中未說明的符號(hào)和術(shù)語見文獻(xiàn)[14]。

關(guān)于兩個(gè)圖的星色數(shù)與他們的冠積的星色數(shù)之間的關(guān)系， 有以下定理2.1。

定理2.1 Xs（G·H）≤Xs（G）+Xs（H）。

證明 記Xs（G）=s。只需證明G·H存在一個(gè)（s+r）-星染色?，F(xiàn)在，分兩步構(gòu)造G·H的一個(gè)星染色：首先，用s種顏色對(duì)G·H中G的拷貝進(jìn)行星染色，該染色記為σ1; 其次，用另外r種新的顏色分別對(duì)G·H中H的每一個(gè)拷貝Hi進(jìn)行星染色，該染色記為σ2。并將σ1與σ2合并，記為σ。顯然，σ1是G·H的一個(gè)（s+r）-正常點(diǎn)染色。

現(xiàn)在證明G·H中不包含4階的2色路。任取G·H中的一個(gè)4階路P4，顯然，要么|V（P4）∩V（G）|或4，要么1≤|V（P4）∩V（G）|≤3。對(duì)于前者，由于σ1與σ2是分別限制在G和H的拷貝上的星染色，則不P4是2色路;對(duì)于后者，因?yàn)棣?與σ2所用顏色不同，所以P4不是2色路。因此， Xs（G·H）≤Xs（G）+Xs（H）。

定理2.1的上界是可達(dá)的。如當(dāng)G是星時(shí)定理中等號(hào)成立， 具體證明方法見定理2.2。為證明定理2.2，引入以下引理2.1。

引理2.1 Xs（P2·H）=Xs（H）+2。

證明 當(dāng)G是2階路P2時(shí)，令P2=x1x2。容易證明Xs（P2·H）≥r+2。假設(shè)Xs（P2·H）≤r+1且σ是P2·H的一個(gè)（r+1）-星染色，可以推出矛盾。設(shè)σ（x1）=α，σ（x2）=b顯然，α≠b。由Xs（H）=r可知，H■■和H■■的頂點(diǎn)顏色數(shù)皆為r+1。此時(shí)，存在頂點(diǎn)y■■和y■■，使得σ（y■■）=b，σ（y■■）=α，其中k0，l0∈（0，1，…，n-1），則P2·H中存在4階的2色路，與假設(shè)矛盾。

為證明Xs（P2·H）≤r+2， 分兩步構(gòu)造如下染色σ：首先，用2種顏色對(duì)P2·H中P2的拷貝進(jìn)行染色;其次，用另外r種新的顏色分別對(duì)P2·H中每一個(gè)H的拷貝進(jìn)行星染色。顯然，σ是P2·H的一個(gè)（r+2）-星染色。

定理2.2 Xs（K1，m·H）=Xs（H）+2。

證明 當(dāng)G是m+1階星K1，m時(shí)，令K1，m的頂點(diǎn)集為{x0，x1，…，xm}，其中x0是度為m的頂點(diǎn)，其它頂點(diǎn)度皆為1。由引理2.1可以證明Xs（K1，m·H）≥r+2。為證明Xs（K1，m·H）≤r+2，分兩步構(gòu)造如下染色σ：首先，用2種顏色對(duì)K1，m·H中K1，m的拷貝進(jìn)行星染色;其次，用另外r種新的顏色分別對(duì)K1，m·H中每一個(gè)H的拷貝進(jìn)行星染色。顯然，σ是K1，m·H的一個(gè)（r+2）-星染色。

所以，Xs（K1，m·H）=Xs（H）+2。此時(shí)，Xs（G·H）=Xs（G）+Xs（H）。

定理2.2可以對(duì)命題1.5中結(jié)果進(jìn)行如下推廣： 對(duì)于任意整數(shù)m，n≥2，有Xs（K1，m·Kn）=n+2。

對(duì)于某些特殊圖而言， 定理2.1中不等式嚴(yán)格成立。如G是路或圈時(shí)，Xs（G·H）=Xs（G）+Xs（H）-1，具體證明方法見定理2.3-2.4。

定理2.3 Xs（Pm·H）=Xs（H）+2。

證明 當(dāng)G是m階路Pm時(shí)，令Pm=x0x1…xm-1。由引理2.1可以證明Xs（Pm·H）≥r+2。為證明Xs（Pm·H）≤r+2，分兩步構(gòu)造如下染色σ首先，用顏色（i）r+2對(duì)Pm·H中Pm的拷貝的頂點(diǎn)xi染色，其中i=0，1，…，m-1;其次，用顏色集{（i+j）r+2|1≤j≤r}分別對(duì)Pm·H中每一個(gè)H的拷貝進(jìn)行星染色。顯然，σ是一個(gè)正常點(diǎn)染色。下面證明σ是一個(gè)星染色。

任取Pm·H中的4階路P4，當(dāng)|V（P4）∩V（Pm）|=4或0時(shí)，顯然，P4不是2色路; 當(dāng)|V（P4）∩V（Pm）|=3時(shí)，由于Pm·H中Pm的拷貝的相繼3個(gè)頂點(diǎn)顏色互不相同，顯然，P4不是2色路; 當(dāng)|V（P4）∩V（Pm）|=2時(shí)，P4有兩個(gè)頂點(diǎn)要么在Pm·H中某一個(gè)H的拷貝Hi上， 要么在Pm·H中某2個(gè)H的拷貝Hi，Hj上。對(duì)于前者，由于σ（xi）=（i）r+2≠（i+k）r+2，其中，1≤k≤r則上至少有3個(gè)頂點(diǎn)顏色不同， 即P4不是2色路。對(duì)于后者，不妨假設(shè)j=i+1，此時(shí)，σ（xi）=（i）r+2，σ（xJ）=（i+1）r+2，在Hj上的任意頂點(diǎn)y■■的顏色為（i+k+1）r+2，其中1≤k≤r，顯然，這3個(gè)頂點(diǎn)顏色互不相同，即P4不是2色路; 當(dāng)|V（P4）∩V（Pm）|=1時(shí)，由于P4在Hi上的3個(gè)相繼頂點(diǎn)顏色數(shù)至少為2，且xi的顏色與它們互不相同，則P4不是2色路。

所以，Xs（Pm·H）=Xs（H）+2。此時(shí)，Xs（G·H）=Xs（G）+Xs（H）-1

由定理2.3及引理1.1-1.3可以對(duì)命題1.1-1.4進(jìn)行如下推廣：對(duì)于任意整數(shù)m，n≥2，有Xs（Pm·Kn）=n+2;對(duì)于任意整數(shù)m≥2，n≥3，當(dāng)n≠5時(shí)，Xs（Pm·Cn）=5; 對(duì)于任意整數(shù)m，n≥3，有Xs（Pm·K1，n）=4; 對(duì)于任意整數(shù)m，n1，n2≥2，有Xs（Pm·Kn1n2）=min{n1，n2}+3。

定理2.4 ，Xs（Cm·H）=Xs（H）+2其中m≠5。

證明 當(dāng)G是m階圈Cm時(shí)，令Cm=x0x1…xm-1x0。由引理2.1可以證明Xs（Cm·H）≥r+2。為證明Xs（Cm·H）≤r+2，分兩步構(gòu)造如下染色σ：首先，用顏色0，1，2對(duì)Cm·H中Cm的拷貝進(jìn)行星染色，其染色方法同文獻(xiàn)[3]中定理5; 其次，用顏色3，4，…，r+1和顏色（σ（xi）+1）3分別對(duì)Cm·H中H的每一個(gè)拷貝進(jìn)行星染色。容易證明，σ是一個(gè)星染色。

所以，Xs（Cm·H）=Xs（H）+2（m≠5）。此時(shí)，Xs（G·H）=Xs（G）+Xs（H）-1。

參考文獻(xiàn)：

[1] Grünbaum B. Acyclic Colorings of Planar Graphs [J]. Israel Journal of Mathematics， 1973， 14（4）：390-408.

[2] Vince A. Star chromatic number [J]. Journal of Graph Theory， 1988， 12（4）： 551-559.

[3] Fertin G ， André R， Reed B . On Star Coloring of Graphs[C]. International Workshop on Graphtheoretic Concepts in Computer Science， OAI， 2001.

[4] Albertson M O ， Chappell G G ， Kierstead H A ， et al. Coloring with no 2-Colored s [J].Electronic Journal of Combinatorics， 2004， 11（1）.

[5] Lyons A . Acyclic and star colorings of cographs[J]. Discrete Applied Mathematics， 2011， 159（16）：1842-1850.

[6] Frucht R ， Harary F . On the corona of two graphs[J]. Aequationes Mathematicae， 1970， 4（1-2）：264-264.

[7] Garcia V， Pedro. On the toughness of the corona of two graphs[J]. International Journal of Computer Mathemtics，2011， 88（13）： 2697-2706.

[8] Kuziak D ， Yero I G ， Rodríguez-Velázquez， Juan A. On the strong metric dimension of corona product graphs and join graphs[J]. Discrete Applied Mathematics， 2013， 161（7-8）：1022-1027.

[9] Tavakoli M ， Rahbarnia F ， Ashrafi A R . Studying the corona product of graphs under some graph invariants[J]. Transactions on Combinatorics， 2014.

[10] Abdo H ， Dimitrov D . The irregularity of graphs under graph operations[J]. Discussiones Mathematicae Graph Theory， 2014， 34（2）：263.

[11] Barragán-Ramírez G.A， Gómez C.G， Rodríguez-Velázquez J.A. Closed formulae for the local metric dimension if corona product graphs[J]， Electronic Notes in Discrete Mathematics，2014，46（0）： 27-34.

[12] Pattabiraman K ， Kandan P . Weighted PI index of corona product of graphs[J]. Discrete Mathematics Algorithms and Applications， 2014， 06（04）：1450055.

[13] Rodríguez-Velázquez， Juan A， Barragán-Ramírez， Gabriel A， García Gómez， Carlos. On the Local Metric Dimension of Corona Product Graphs[J]. Bulletin of the Malaysian Mathematical Sciences Society， 2016， 39（1 Supplement）：157-173.

[14] Venkatesan K ， Vivin V ， Mathiyazhagan V . On Star Coloring Of Corona Graphs[J]. Applied Mathematics E Notes， 2015：97-104.

基金項(xiàng)目： 西北民族大學(xué)科研創(chuàng)新團(tuán)隊(duì)計(jì)劃資助，國家民委科研資助項(xiàng)目（14XBZ018）。

作者簡介： 蔡瑾（1997-）， 女， 吉林人， 碩士研究生;田雙亮（1965-）， 男， 教授， 研究方向?yàn)閳D論及組合優(yōu)化。