若干图的冠积的星染色

蔡瑾 田双亮 安卓莫

【摘要】  图G的一个k-星染色σ是使G不存在4阶的2色路的k-点染色， 其中最小的k值称为G的星色数， 记为Xs（G）。 简单图G与H的冠积G·H被定义为将G的第i个顶点与第i个H的拷贝中每一个顶点连接得到的图. 主要研究了任意图G与H的冠积的星色数的上界及某些特殊图G与任意图H的冠积的星色数Xs（G·H）， 具体结果为：Xs（G·H）≤Xs（G）+Xs（H） ; 当G为m阶路时， Xs（Pm·H）=Xs（H）+2; 当G为m+1解星时， Xs（K1，m·H）=Xs（H）+2; 当G为m≠5阶圈时，Xs（Cm·H）=Xs（H）+2 。

【关键词】冠积  星染色  路  星  圈

一、引言

本文所考虑的图都是有限无向的简单连通图，记（m）n=m（modn）， 其中m为整数，n为整数。

图的点染色是图论中的重要内容，图的正常点染色仅要求任意两个相邻的顶点所染的颜色不同，对点染色的要求不同，就会有不同的染色形式. 随着对点染色的染色形式的广泛推广，提出了许多有意义的染色形式。图G的一个k-星染色σ是使G中不存在4阶的2色路的k-点染色， 其中最小的k值称为G的星色数，记为Xs（G）， 该染色是由Grünbaum在文献[1]中提出来的. 这种染色方式在许多文章中被研究，如Vinve在文献[2]中推广了图的染色问题并以另一种形式引入了星染色的概念; Fertin等人在文献[3]中确定了特殊图的星色数的精确值以及部分图的星色数的界; Albertson等人在文献[4]中证明了平面图的星色数最多不超过20; Lyons在文献[5]中证明了图的无圈染色也是一个星染色，且给出了一个寻找图的最优星染色的线性算法。

在下文的討论中将用到如下引理1.1-1.3。

引理1.1 对于任意整数n≥3，当n≠5时，Xs（Cn）=3， 否则Xs（Cn）=4。

引理1.2 对于任意整数n，m≥2，Xs（Kn，m）=min{m，n}+1。

引理1.3 对于任意整数m≥3，Xs（Km）=m。

图的运算是研究图的构造的重要工具，其运算方式有许多， 常见的图的运算有冠积、直积、强积、半强积等，其中m阶图G和n阶图H的冠积G·H被定义为取G的1个拷贝， H的m个拷贝，并将G的第i个顶点与第i个H的每一个顶点连接得到的图， 这种运算方式是由Harary和Frucht于1970年在文献[6]中提出的。对于图的冠积运算研究有许多， 文献[7-13]都对不同图的冠积运算的性质进行了研究. 本文将对特殊图与任意图的冠积的星染色进行研究。

Venkatesan在文献[14]中分别给出了n阶路与n阶完全图， 阶圈，n+1阶星， n1+n2阶完+1全二部图及n=阶星与n阶完全图的星色数，其主要研究结果如下：

命题1.1 对于任意n≥2，Xs（Pn·Kn）=n+2.n

命题1.2 对于任意n≥3， 若n=5则Xs（Pn·Cn）=6; 否则，Xs（Pn·Cn）=5。

命题1.3 对于任意正整数n≥3，Xs（Pn·K1，n）=4。

命题1.4 对于任意n≥2且n=n1或n=n2，Xs（Pn·Kn1，n2）=min{n1+n2}+3。

命题1.5 对于任意n≥3，Xs（K1，n·Kn）=n+2。

文献[14]主要研究同阶特殊图的冠积的星色数，本文对其结果进行推广，分别得到了m阶路以及m+1阶星与任意简单图的星色数.同时又研究了m阶圈与任意简单图的星色数，并给出了对应的染色方法.

二、主要结果及其证明

设G和H是阶数分别为m，n的图，其中m，n≥2， 且Xs（H）=r。记G，H和G·H中H的每一个拷贝Hi的顶点集分别为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■■））。文中未说明的符号和术语见文献[14]。

关于两个图的星色数与他们的冠积的星色数之间的关系， 有以下定理2.1。

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

证明 记Xs（G）=s。只需证明G·H存在一个（s+r）-星染色。现在，分两步构造G·H的一个星染色：首先，用s种颜色对G·H中G的拷贝进行星染色，该染色记为σ1; 其次，用另外r种新的颜色分别对G·H中H的每一个拷贝Hi进行星染色，该染色记为σ2。并将σ1与σ2合并，记为σ。显然，σ1是G·H的一个（s+r）-正常点染色。

现在证明G·H中不包含4阶的2色路。任取G·H中的一个4阶路P4，显然，要么|V（P4）∩V（G）|或4，要么1≤|V（P4）∩V（G）|≤3。对于前者，由于σ1与σ2是分别限制在G和H的拷贝上的星染色，则不P4是2色路;对于后者，因为σ1与σ2所用颜色不同，所以P4不是2色路。因此， Xs（G·H）≤Xs（G）+Xs（H）。

定理2.1的上界是可达的。如当G是星时定理中等号成立， 具体证明方法见定理2.2。为证明定理2.2，引入以下引理2.1。

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

证明 当G是2阶路P2时，令P2=x1x2。容易证明Xs（P2·H）≥r+2。假设Xs（P2·H）≤r+1且σ是P2·H的一个（r+1）-星染色，可以推出矛盾。设σ（x1）=α，σ（x2）=b显然，α≠b。由Xs（H）=r可知，H■■和H■■的顶点颜色数皆为r+1。此时，存在顶点y■■和y■■，使得σ（y■■）=b，σ（y■■）=α，其中k0，l0∈（0，1，…，n-1），则P2·H中存在4阶的2色路，与假设矛盾。

为证明Xs（P2·H）≤r+2， 分两步构造如下染色σ：首先，用2种颜色对P2·H中P2的拷贝进行染色;其次，用另外r种新的颜色分别对P2·H中每一个H的拷贝进行星染色。显然，σ是P2·H的一个（r+2）-星染色。

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

证明 当G是m+1阶星K1，m时，令K1，m的顶点集为{x0，x1，…，xm}，其中x0是度为m的顶点，其它顶点度皆为1。由引理2.1可以证明Xs（K1，m·H）≥r+2。为证明Xs（K1，m·H）≤r+2，分两步构造如下染色σ：首先，用2种颜色对K1，m·H中K1，m的拷贝进行星染色;其次，用另外r种新的颜色分别对K1，m·H中每一个H的拷贝进行星染色。显然，σ是K1，m·H的一个（r+2）-星染色。

所以，Xs（K1，m·H）=Xs（H）+2。此时，Xs（G·H）=Xs（G）+Xs（H）。

定理2.2可以对命题1.5中结果进行如下推广： 对于任意整数m，n≥2，有Xs（K1，m·Kn）=n+2。

对于某些特殊图而言， 定理2.1中不等式严格成立。如G是路或圈时，Xs（G·H）=Xs（G）+Xs（H）-1，具体证明方法见定理2.3-2.4。

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

证明 当G是m阶路Pm时，令Pm=x0x1…xm-1。由引理2.1可以证明Xs（Pm·H）≥r+2。为证明Xs（Pm·H）≤r+2，分两步构造如下染色σ首先，用颜色（i）r+2对Pm·H中Pm的拷贝的顶点xi染色，其中i=0，1，…，m-1;其次，用颜色集{（i+j）r+2|1≤j≤r}分别对Pm·H中每一个H的拷贝进行星染色。显然，σ是一个正常点染色。下面证明σ是一个星染色。

任取Pm·H中的4階路P4，当|V（P4）∩V（Pm）|=4或0时，显然，P4不是2色路; 当|V（P4）∩V（Pm）|=3时，由于Pm·H中Pm的拷贝的相继3个顶点颜色互不相同，显然，P4不是2色路; 当|V（P4）∩V（Pm）|=2时，P4有两个顶点要么在Pm·H中某一个H的拷贝Hi上， 要么在Pm·H中某2个H的拷贝Hi，Hj上。对于前者，由于σ（xi）=（i）r+2≠（i+k）r+2，其中，1≤k≤r则上至少有3个顶点颜色不同， 即P4不是2色路。对于后者，不妨假设j=i+1，此时，σ（xi）=（i）r+2，σ（xJ）=（i+1）r+2，在Hj上的任意顶点y■■的颜色为（i+k+1）r+2，其中1≤k≤r，显然，这3个顶点颜色互不相同，即P4不是2色路; 当|V（P4）∩V（Pm）|=1时，由于P4在Hi上的3个相继顶点颜色数至少为2，且xi的颜色与它们互不相同，则P4不是2色路。

所以，Xs（Pm·H）=Xs（H）+2。此时，Xs（G·H）=Xs（G）+Xs（H）-1

由定理2.3及引理1.1-1.3可以对命题1.1-1.4进行如下推广：对于任意整数m，n≥2，有Xs（Pm·Kn）=n+2;对于任意整数m≥2，n≥3，当n≠5时，Xs（Pm·Cn）=5; 对于任意整数m，n≥3，有Xs（Pm·K1，n）=4; 对于任意整数m，n1，n2≥2，有Xs（Pm·Kn1n2）=min{n1，n2}+3。

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

证明 当G是m阶圈Cm时，令Cm=x0x1…xm-1x0。由引理2.1可以证明Xs（Cm·H）≥r+2。为证明Xs（Cm·H）≤r+2，分两步构造如下染色σ：首先，用颜色0，1，2对Cm·H中Cm的拷贝进行星染色，其染色方法同文献[3]中定理5; 其次，用颜色3，4，…，r+1和颜色（σ（xi）+1）3分别对Cm·H中H的每一个拷贝进行星染色。容易证明，σ是一个星染色。

所以，Xs（Cm·H）=Xs（H）+2（m≠5）。此时，Xs（G·H）=Xs（G）+Xs（H）-1。

参考文献：

[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.

基金项目： 西北民族大学科研创新团队计划资助，国家民委科研资助项目（14XBZ018）。

作者簡介： 蔡瑾（1997-）， 女， 吉林人， 硕士研究生;田双亮（1965-）， 男， 教授， 研究方向为图论及组合优化。