兩個(gè)最大度為2的圖的邊冠積的無圈邊染色

摘要：圖G的無圈邊染色是指G的任意兩個(gè)色類的導(dǎo)出子圖不含2-色圈的正常邊染色，G的無圈邊染色所用最少的顏色數(shù)稱為G的無圈邊色數(shù).證明了兩個(gè)最大度為2的圖的邊冠積的無圈邊色數(shù)等于其最大度.

關(guān)鍵詞：邊冠積;二部圖;無圈邊染色;無圈邊色數(shù)

中圖分類號(hào)：O 157.5""" 文獻(xiàn)標(biāo)志碼：A""" 文章編號(hào)：1001-988Ⅹ（2024）05-0120-05

Acyclic edge coloring for the edge corona product of

two graphs with maximum degree two

JIN Mei-qin，TIAN Shuang-liang

（School of Mathematics and Computer Science，Northwest Minzu University，Lanzhou 730030，Gansu，China）

Abstract：An acyclic edge coloring of a graph G is a proper edge coloring such that the subgraph induced by any two color classes is not bichromatic（2-colored） cycles.The acyclic chromatic index of G is the least number of colors required in an acyclic edge coloring of G.In this paper，it is proved that the acyclic chromatic index of the edge corona product of two graphs of maximum degree 2 is equal to its maximum degree.

Key words：edge corona product;bipartite graph;acyclic edge coloring;acyclic chromatic index

本文研究的圖均為有限無向的簡(jiǎn)單圖，用V（G）與E（G）分別表示圖G的頂點(diǎn)集和邊集，Δ（G）表示圖G的最大度.為敘述方便，記（x）k=x（mod k），其中x為整數(shù)，k為正整數(shù).文中未說明的術(shù)語與符號(hào)見參考文獻(xiàn)［1］.

圖G的一個(gè)k-正常邊染色σ是指E（G）的一個(gè)劃分（E1，E2，…，Ek），其中每個(gè)Ei均為匹配.稱Ei為σ的一個(gè)色類，最小的k值稱為圖G的邊色數(shù)，并記為χ′（G）.設(shè)σ=（E1，E2，…，Ek）為圖G的一個(gè)k-正常邊染色，若σ的任意兩個(gè)不同色類的導(dǎo)出子圖是森林，即G中不含雙色圈，則稱σ為圖G的一個(gè)k-無圈邊染色，并稱最小的k值為圖G的無圈邊色數(shù)，記為a′（G）.

1978年，F(xiàn)iamcˇik［2］提出了無圈邊染色的概念，并提出了著名的無圈邊染色猜想：對(duì)于任意圖G，有a′（G）≤Δ（G）+2.此猜想在2001年被Alon等［3］再次提及，自此以后，這一猜想得到了更多學(xué)者的關(guān)注.目前已經(jīng)證明這一猜想對(duì)圍長(zhǎng)很大的圖、特殊的等完全二部圖、正則圖、2-退化圖以及特殊的平面圖是成立的，并且對(duì)于一些較特殊的圖類，可得到更小的上界［4-16］.根據(jù)Vizing定理，對(duì)任意簡(jiǎn)單圖G，有Δ（G）≤χ′（G）≤Δ（G）+1.當(dāng)χ′（G）=Δ（G）時(shí)，稱G為第一類的；當(dāng)χ′（G）≤Δ（G）+1時(shí)，稱G為第二類的.由圖的正常邊染色與無圈邊染色的概念，顯然對(duì)任意圖G有χ′（G）≤a′（G），那么對(duì)某些圖類是否有a′（G）=χ′（G）？Basavaraju等［5-7］證明特殊的完全二部圖的無圈邊色數(shù)為Δ（G）+2，F(xiàn)iedorowicz［13］、Cohen［14］和Hou［15］等證明了一些特殊的平面圖以及特殊的完全細(xì)分圖可以使以上等式成立.

引理1 設(shè)H為G的子圖，則a′（H）≤a′（G）.

證明 顯然，對(duì)于圖G的任意一個(gè)無圈邊染色，限制在其子圖H上后仍是無圈的." 】

引理2 對(duì)于具有連通分支G1，G2，…，Gω的圖G，有a′（G）=max{a′（G1），a′（G2），…，a′（Gω）}.

證明 顯然，a′（G）≤max{a′（G1），a′（G2），…，a′（Gω）}，由引理1可知，a′（G）≥max{a′（G1），…，a′（Gω）}." 】

常見的圖運(yùn)算有倍圖［17，18］、笛卡爾積［19］、直積［20，21］等，本文利用圖的邊冠積［22］構(gòu)造兩種第一類圖，并證明其無圈邊色數(shù)等于其最大度.

定義1 設(shè)G是邊集為{e0，e1，…，em-1}的圖，H0，H1，…，Hm-1是圖H的m個(gè)拷貝.G與H的邊冠積［22］GH是指將圖G中每一條邊ei的兩個(gè)端點(diǎn)與H的第i個(gè)的拷貝Hi的所有頂點(diǎn)相連接得到的圖.

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

根據(jù)圖的邊冠積的定義，GH可分解成三個(gè)邊不交子圖G，G1，G2的并，即

GH=G∪G1∪G2，（1）

其中

G1=∪m-1i=0H′i，

G2=∪m-1i=0Hi，

且H′i表示圖G中的邊ei的端點(diǎn)與V（Hi）中的頂點(diǎn)之間的邊在GH中的導(dǎo)出子圖.顯然，每一個(gè)H′i是一個(gè)二部圖，且對(duì)任意兩個(gè)不同的自然數(shù)i=0，1，…，n-1及j=0，1，…，m-1，有H′iH′j且邊不交，Hi與Hj不相交.

設(shè)Cn=x0x1…xn-1x0，Cm=y0y1…ym-1y0.那么CnCm中的邊xixj對(duì)應(yīng)的拷貝Hi的頂點(diǎn)集V（Hi）={yi0，yi1，…，yim-1}，邊集E（Hi）={yi0yi1，yi1yi2，…，yim-2yim-1，yim-1yi0}.此時(shí)（1）式中的G1是一個(gè)（2m，2）-雙正則二部圖［23］.

引理3 a′（G1）=Δ（G1）.

證明 顯然，a′（G1）≥Δ（G1），故僅需證明a′（G1）≤Δ（G1）=2m.構(gòu)造G1的邊染色σ，令

σ1（xiyi-1j）=m+j， σ1（xiyij）=j，

i=1，2，…，n-2， j=0，1，…，m-1;

σ2（x0yn-1m-1）=σ2（xn-1yn-1m-1）=m;

σ2（x0y0j）=σ2（xn-1yn-1j）=j，

j=0，1，…，m-1;

σ2（x0yn-1j）=σ2（xn-1yn-2j）=m+j+1，

j=0，1，…，m-2.

將σ1，σ2合并記為σ.顯然，σ使用了2m種顏色，記所用顏色集S=S1∪S2，其中S1={0，1，…，m-1}，S2={m，m+1，…，2m-1}.下面證明σ是G1的無圈邊染色.

首先，證明σ是G1的正常邊染色.任取頂點(diǎn)v∈V（G1），則v=xi或v=yij，i=0，1，…，n-1，j=0，1，…，m-1.由σ的定義可知，其關(guān)聯(lián)邊可能染的顏色為：j，m，m+j，m+j+1.顯然G1的任一頂點(diǎn)的關(guān)聯(lián)邊均染不同的顏色，故σ是G1的正常邊染色.

現(xiàn)在證明σ是G1的無圈邊染色.任取c1，c2∈S，c1≠c2，設(shè)σ（uv）=c1，σ（vw）=c2.由σ的定義可知，若染顏色c1，c2的邊在G1中的導(dǎo)出子圖有2-色圈，則{c1，c2}∩S1=1.不妨設(shè)c1∈S1，c2∈S2，則u，v，w的取法如下：

取法Ⅰ.設(shè)u=xi，v=yij，w=xi+1，其中i=0，1，…，n-2， j=0，1，…，m-1;

取法Ⅱ.設(shè)u=xij，v=xi+1，w=xi+1j，其中i=0，1，…，n-2， j=0，1，…，m-1，或設(shè)u=xn-1j，v=xk，w=xkj，k=0，n-1， j=0，1，…，m-1.

討論取法Ⅰ，取法Ⅱ可類似討論.由σ的定義，當(dāng)i=0，1，…，n-3時(shí)，c1=j，c2=m+j.在頂點(diǎn)u的關(guān)聯(lián)邊中，染顏色c2的邊為uu1=xiyi-1j，在頂點(diǎn)u1的關(guān)聯(lián)邊中，染顏色c1的邊為u1u2=yi-1jxi-1.類似地，在頂點(diǎn)w的關(guān)聯(lián)邊中，染顏色c1的邊為ww1=xi+1yi+1j.重復(fù)以上過程，可得到一條“折線”狀的路，路的兩個(gè)端點(diǎn)分別為yn-2j和yn-1j′，其中j≠j′.當(dāng)i=n-2時(shí)，不妨設(shè)u=xn-2，v=yn-1j，w=xn-1.由σ的定義，c1=j，當(dāng)j=0，1，…，m-2時(shí)，c2=m+j+1，當(dāng)j=m-1時(shí)，c2=m，此時(shí)，頂點(diǎn)u的關(guān)聯(lián)邊中，染顏色c1的邊為uu1=xn-2yn-2j+1，但頂點(diǎn)u1的關(guān)聯(lián)邊染的顏色不為c2.顯然，此時(shí)染顏色c1，c2的邊在G1中的導(dǎo)出子圖不含2-色圈.因此，σ是G1的無圈邊染色，故a′（G1）≤Δ（G1）.

綜上可知，a′（G1）=Δ（G1）." 】

設(shè)G是具有連通分支N1，N2，…，Nω的最大度為2的圖，H是具有連通分支M1，M2，…，Mt的最大度為2的圖，V（G）=n，V（H）=m，則關(guān)于GH的無圈邊染色有以下結(jié)果.

定理1 設(shè)G，H是任意兩個(gè)最大度為2的圖，則a′（GH）=Δ（GH）.

證明 顯然，a′（GH）≥Δ（GH），因此僅需證明a′（GH）≤Δ（GH）=2m+2.按照G和H的結(jié)構(gòu)，分以下情形證明：

情形1 w=1，t=1.分以下情形分別討論：

情形1.1 GCn，HCm.

記=CnCm，Cim=Hi.根據(jù)（1）式分三步構(gòu)造的邊染色.

首先，對(duì)Cn中的邊進(jìn)行染色，具體地，令

σ1（x0xn-1）=m;

σ1（xixi+1）=2m+（i+1）2， i=0，1，…，n-2.

其次，對(duì)G1中的邊進(jìn)行染色，具體地，令

σ2（xiyij）=j， σ2（xiyi-1j）=m+j，

i=1，2，…，n-2， j=0，1，…，m-1；

σ2（x0y0j）=σ2（xn-1yn-1j）=j，

σ2（x0yn-1j）=m+j+1，

j=0，1，…，m-1;

σ2（xn-1yn-2m-1）=（n）2+2m，

σ2（xn-1yn-2j）=m+j+1，

j=0，1，…，m-2.

最后，對(duì)C2中的邊進(jìn)行染色，具體地，令

σ3（yi0yim-1）=1， i=0，1，…，n-1;

σ3（yijyij+1）=2m+（m+j+1）2，

i=0，1，…，n-2;

σ3（yn-2jyn-2j+1）=2m+（m+n+j+1）2，

j=0，1，…，m-2.

將σ1，σ2，σ3合并記為σ.顯然，σ使用了2m+2種顏色，記所使用的顏色集為S=S1∪S2，其中S1={0，1，…，2m-1}，S2={2m，2m+1}.下面證明σ是的無圈邊染色.

首先，證明σ是的正常邊染色.任取頂點(diǎn)v∈V（），要么v=xi，要么v=yij，i=0，1，…，

n-1， j=0，1，…，m-1.若v=xi，則由σ的定義可知，其關(guān)聯(lián)邊可能染的顏色為：j，m，m+j，m+j+1，2m，2m+1，而染顏色m+j+1的邊和染顏色2m的邊有共同的頂點(diǎn)xi時(shí)，j=0，1，…，m-2.因此xi的關(guān)聯(lián)邊均染不同的顏色.若v=yij，則由σ的定義可知，其關(guān)聯(lián)邊可能染的顏色為：j，m+j，m+j+1，2m，2m+1，且σ（xiyi1）=1，σ（yi0yim-1）=1;染顏色m+j+1的邊和染顏色2m的邊不會(huì)存在共同的頂點(diǎn)yij.所以，σ是的正常邊染色.

其次，證明σ是的無圈邊染色.任取c1，c2∈S，c1≠c2，設(shè)σ（uv）=c1，σ（vw）=c2.根據(jù)c1，c2所屬的顏色集，分以下三種情形進(jìn)行討論：

情形1.1.1 c1，c2∈S1.此時(shí)u，v，w的可能取法如下：

取法Ⅰ.若v∈V（Cn），則存在i=0，1，…，n-1，使得{u，w}∩V（Cim）=2或1.若{u，w}∩V（Cim）=2，則結(jié)合σ的定義和引理1可知，此時(shí)染顏色c1，c2邊在中的導(dǎo)出子圖不含2-色圈.若{u，w}∩V（Cim）=1，則不妨設(shè)u=ykj，v=x0，w=xn-1，k=0，n-1.由σ的定義，c2=m，c1=j或m+j+1.若c1=j，則u=y0i，當(dāng)j≠0時(shí)，頂點(diǎn)u的關(guān)聯(lián)邊中沒有染顏色c2的邊;當(dāng)j=0時(shí)，頂點(diǎn)w的關(guān)聯(lián)邊中染顏色c1的邊為ww1=xn-1yn-10，頂點(diǎn)w1的關(guān)聯(lián)邊中沒有染顏色c2的邊;若c1=m+j+1，則u=yn-1j，j=0，1，…，m-2，此時(shí)頂點(diǎn)u的關(guān)聯(lián)邊中沒有染顏色c2的邊.因此，在該情況下染顏色c1，c2的邊在中的導(dǎo)出子圖不會(huì)形成2-色圈.

取法Ⅱ.任取i=0，1，…，n-1，若v∈V（Cim），那么{u，w}∩V（Cim）=0或1.若{u，w}∩V（Cim）=0，則結(jié)合σ的定義和引理1可知，此時(shí)染顏色c1，c2的邊在中的導(dǎo)出子圖是不含2-色圈的;若{u，w}∩V（Cim）=1，則不妨設(shè)u=yim-1，v=yi0，w=xi.由σ的定義，c1=1，c2=0.此時(shí)頂點(diǎn)u的關(guān)聯(lián)邊中沒有染顏色c2的邊，顯然，此時(shí)染顏色c1，c2的邊在中的導(dǎo)出子圖是路.

所以，當(dāng)c1，c2∈S1時(shí)，染顏色c1，c2的邊在中的導(dǎo)出子圖不會(huì)形成2-色圈.

情形1.1.2 c1，c2∈S2.

不妨設(shè)c1=2m，c2=2m+1.此時(shí)u，v，w有兩種取法，即{u，v，w}V（Cim）或{u，v，w}V（Cn）.若{u，v，w}V（Cim），i=0，1，…，n-2，則由σ的定義，顯然，染顏色c1，c2的邊在中的導(dǎo)出子圖是路.若{u，v，w}V（Cn）或{u，v，w}V（Cn-1m），則不妨設(shè)u=xi-1，v=xi，w=xi+1.此時(shí)，頂點(diǎn)u的關(guān)聯(lián)邊中染顏色c2的邊為uu1=xi-1xi-2，頂點(diǎn)w的關(guān)聯(lián)邊中染顏色c1的邊為ww1=xi+1xi+2.重復(fù)以上過程，可得到一條端點(diǎn)分別是yn-20，yn-10的路.所以，當(dāng)c1，c2∈S2時(shí)，染顏色c1，c2的邊在中的導(dǎo)出子圖是路.

情形1.1.3 {c1，c2}∩S1=1.

不妨設(shè)c1∈S1，c2∈S2，則c2=2m或c2=2m+1.僅討論c2=2m的情形，c2=2m+1的情形類似.當(dāng)c2=2m時(shí)，u，v，w的可能取法如下：

取法Ⅰ.對(duì)任意i=1，2，…，n-2，設(shè)u=yij，v=xi，w=xi+1，（i+1）2=0;或設(shè)u=y0j，v=x0，w=yn-1m-1.由σ的定義可知，此時(shí)c1=j，c2=2m.當(dāng)u=yij，v=xi，w=xi+1，（i+1）2=0時(shí)，頂點(diǎn)u的關(guān)聯(lián)邊中染顏色c2的邊為uu1=yijyij+1或uu1=yijyij-1，頂點(diǎn)u1的關(guān)聯(lián)邊中如果有染顏色c1的邊u1u2，則u1u2=yi1yim-1，頂點(diǎn)u2的關(guān)聯(lián)邊中沒有染顏色c2的邊.當(dāng)u=y0j，v=x0，w=yn-1m-1時(shí)，若j=0，2，…，m-2，頂點(diǎn)w的關(guān)聯(lián)邊中沒有染顏色c1的邊.若j=1且m為奇數(shù)，則頂點(diǎn)u的關(guān)聯(lián)邊中染顏色c2的邊為uu1=y01y00，頂點(diǎn)u1的關(guān)聯(lián)邊中染顏色c1的邊為u1u2=y00y0m-1，頂點(diǎn)u2的關(guān)聯(lián)邊中沒有染顏色c2的邊.若j=1且m為偶數(shù)，則頂點(diǎn)u的關(guān)聯(lián)邊中染顏色c2的邊為uu1=y01y02，頂點(diǎn)u1的關(guān)聯(lián)邊中沒有染顏色c1的邊.若j=m-1，則頂點(diǎn)u的關(guān)聯(lián)邊中沒有染顏色c2的邊.所以此時(shí)染顏色c1，c2的邊在中的導(dǎo)出子圖不會(huì)形成2-色圈.

取法Ⅱ.設(shè)u=yi-1j，v=xi，w=xi+1，其中i=1，2，…，n-2且（i+1）2=0.由σ的定義可知，此時(shí)c1=m+j，c2=2m.此時(shí)頂點(diǎn)u的關(guān)聯(lián)邊中染顏色c2的邊為uu1=yi-1jyi-1j+1或uu1=yi-1jyi-1j-1，頂點(diǎn)u1的關(guān)聯(lián)邊中沒有染顏色c1的邊.顯然染顏色c1，c2的邊在中的導(dǎo)出子圖是路.

取法Ⅲ.設(shè)u=xn-1，v=x0，w=yn-1m-1.由σ的定義，c1=m，c2=2m.此時(shí)頂點(diǎn)w的關(guān)聯(lián)邊中沒有染顏色c1的邊.顯然，此時(shí)染顏色c1，c2的邊在中的導(dǎo)出子圖是路.

所以，當(dāng){c1，c2}∩S1=1時(shí)，染顏色c1，c2的邊在中的導(dǎo)出子圖不會(huì)形成2-色圈.

綜上分析，σ是的無圈邊染色，即GCn，H≈Cm時(shí)，a′（GH）≤2m+2.

情形1.2 GCn，HPm或GPn，HCm或GPn，HPm.

由引理1和情形1.1可知，此時(shí)，a′（GH）≤2m+2.

情形2 ω=1，t≥2.

情形2.1 GCn，MtCnt，n1+n2+…+nt=m.

對(duì)Mt進(jìn)行排序，設(shè)V（M1）={y0，y1，…，yn1-1}，V（M2）={yn1，yn1+1，yn1+n2-1}，…，V（Mt）={yn1+n2+…+nt-1，yn1+n2+…+nt-1+1，…，ym-1}，

即V（H）={y0，y1，…，ym-1}，E（H）=E（Cn1）∪E（Cn2）

∪…∪E（Cnt）.記=CnH.

設(shè)E1=

{yn1-1yn1，

yn1+n2-1yn1=n2，…，yn1+n2+…+nt-1

yn1+n2+…+nt-1+1，

y0ym-1}，

E2={y0yn1-1，yn1yn1+n2-1，…，yn1+n2+…+nt-1ym-1}.

由H的定義知，V（H）=V（Cm），E（H）=（E（Cm）-E1）∪E2.即V（）=V（），E（）=（E（）-E1）∪E2.

結(jié)合“情形1.1”中的無圈邊染色σ，可構(gòu)造的邊染色β：令

β1（E（）-E1）=σ（E（）-E1）， β2（E2）=1.

將β1，β2合并記為β.顯然，β使用了2m+2種顏色，記所使用的顏色集S={0，1，…，2m+1}.下面證明β是的無圈邊染色.

首先證明β是的正常邊染色.由于σ是的無圈邊染色，由β的定義，任取頂點(diǎn)v∈V（），若頂點(diǎn)v的關(guān)聯(lián)邊uv，vw同色，則β（uv）=β（vw）=1，而β（xiyi1）=1，β（yi0yin1-1）=1，

β（yin1yin1+n2-1）=1，…，β（yin1+n2+…+nt-1yim-1）=1.顯然染顏色1的邊沒有公共的頂點(diǎn)，因此β是的正常邊染色.

下面證明β是的無圈邊染色.任取c1，c2∈S，c1≠c2，取{u，v，w}∈V（），設(shè)β（uv）=c1，β（vw）=c2.因?yàn)棣沂堑臒o圈邊染色，由β的定義可知，若染顏色c1，c2的邊在中的導(dǎo)出子圖可以形成2-色圈，那么{c1，c2}∩S={1}，不妨設(shè)c1=1，按照邊uv所屬的邊集分以下兩種情形討論：

情形Ⅰ.uv∈（E（）-E1）∪{y1yin1-1}.此時(shí)uv∈E（CnCn1），結(jié)合情形1的討論及β的定義可知，此時(shí)染顏色c1，c2的邊在中的導(dǎo)出子圖不會(huì)形成2-色圈.

情形Ⅱ.uv∈E1且uv≠yi1yin1-1.不妨設(shè)u=yin1，v=yin1+n2-1，此時(shí)頂點(diǎn)w的可能取法如下：當(dāng)i=0，1，…，n-2時(shí)，w∈{yin1+n2-2，xi，xi+1}，當(dāng)i=n-1時(shí)，w∈{yn-1n1+n2-2，xn-1，x0}.由β的定義可知，c2∈{2m，2m+1，n1+n2-1，m+n1+n2-1}，當(dāng)c2∈{n1+n2-1，m+n1+n2-1}時(shí)，頂點(diǎn)u的關(guān)聯(lián)邊中沒有染顏色c2的邊.當(dāng)c2∈{2m，2m+1}時(shí)，頂點(diǎn)u的關(guān)聯(lián)邊中如果有染顏色c2的邊，不妨設(shè)β（uu1）=c2，設(shè)uu1=yin1yin1+1，但是頂點(diǎn)u1的關(guān)聯(lián)邊中沒有染顏色c1的邊.顯然uv∈E1且uv≠yi1yin1-1時(shí)，染顏色c1，c2的邊在中的導(dǎo)出子圖是路.

因此，任取c1，c2∈S，c1≠c2，則染顏色c1，c2的邊在中的導(dǎo)出子圖不會(huì)形成2-色圈，故β是的無圈邊染色.即GCn，HtCnt，且n1+n2+…+nt=m時(shí)，a′（GH）≤Δ（GH）.

情形2.2 G和H的結(jié)構(gòu)可分為以下情況：

GCn，MrCnr，MtPnt，∑（nr+nt）=m或

GPn，MrCnr，MtPnt，∑（nr+nt）=m

或GPn，MrPnr，MtPnt，∑（nr+nt）=m，

則由引理1和情形2.1可知，此時(shí)a′（GH）≤2m+2.

情形3 ω≥2，t=1.

由引理2和情形1可知，此時(shí)a′（GH）≤2m+2.

情形4 ω≥2，t≥2.

結(jié)合引理1，引理2和情況2可知，此時(shí)a′（GH）≤2m+2.

綜合以上分析可知，當(dāng)G，H是任意兩個(gè)最大度為2的圖時(shí)，a′（GH）=Δ（GH）." 】

參考文獻(xiàn)：

［1］ BONDY J，MURTY U S R.Graph Theory with Application［M］.New York：American Elsevier，1976.

［2］ FIAMCˇIK J.The acyclic chromatic class of a graph［J］.Math Slovaca，1978，28（2）：139.

［3］ ALON N，SUDAKOV B，ZAKS A.Acyclic edge colorings of graphs［J］.J Graph Theory，2001，37（3）：157.

［4］ BASAVARAJU M，CHANDRAN L S，KUMMINI M.d-regular graphs of acyclic chromatic index at least d+2［J］.J Graph The，2010，63（3）：226.

［5］ BASAVARAJU M，CHANDRAN L S.A note on acyclic edge coloring of complete bipartite graphs［J］.Discrete Math，2009，309（13）：4646.

［6］ VENKATESWARLU A，SARKAR S.On acyclic edge coloring of the complete bipartite graphs K2p-1，2p-1 for odd prime p［J］.Discrete Math，2016，339（1）：72.

［7］ VENKATESWARLU A，SARKAR S，ANANTHANAR-AYANAN S M.On acyclic edge coloring of complete bipartite graphs［J］.Discrete Math，2017，340（3）：481.

［8］ MIECZYSLAW B，ANNA F.Acyclic edge coloring of planar graphs without short cycles［J］.Discrete Math，2010，310（9）：1445.

［9］ HOU J，LIU G，WU J.Acyclic edge coloring of planar graphs without small cycles［J］.Graph Combinator，2012，28（2）：215.

［10］ YU D，HOU J，LIU G，et al.Acyclic edge coloring of planar graphs with large girth［J］.Theor Comput Sci，2009，410（47-49）：5196.

［11］ HOU J，WANG W，ZhANG X.Acyclic edge coloring of planar graphs with girth at least 5［J］.Discrete Appl Math，2013，161（18）：2958.

［12］ BASAVARAJU M，CHANDRAN L S.Acyclic edge coloring of 2-degenerate graphs［J］.J Graph Theory，2012，69（1）：1.

［13］ FIEDOROWICZ A，HAL/USZCZAK M.Acyclic chromatic indices of fully subdivided graphs［J］.Information Processing Letters，2012，112（13）：557.

［14］ COHEN N，HAVET F，MLLER T.Acyclic edge-colouring of planar graphs.Extended abstract［J］.Electron Notes Discrete Math，2009，34：417.

［15］ HOU J，LIU G，WANG G.Improved bounds for acyclic chromatic index of planar graphs［J］.Discrete Appl Math，2011，159（8）：876.

［16］ HUDK D，KARDO F，LUAR B，et al.Acyclic edge coloring of planar graphs with"" colors［J］.Discrete Appl Math，2012，160（9）：1356.

［17］ 張忠輔，仇鵬翔，張東翰，等.圖的倍圖與補(bǔ)倍圖（英文）［J］.數(shù)學(xué)進(jìn)展，2008（3）：313.

［18］ 王同昕，楊超，殷志祥，等.若干倍圖的2-距離和可區(qū)別全染色［J］.西北師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2023，59（5）：47.

［19］ XU J，YANG C.Connectivity of Cartesian product graphs［J］.Discrete Math，2006，306（1）：159.

［20］ JHA P，KLAVZAR S.Independence in direct product graphs［J］.Ars Combinatria，1999，50：53.

［21］ 董曉媛，馬登革.Km和Pn的直積的交叉數(shù)［J］.西北師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，53（4）：23.

［22］ WANG S，ZHOU B.The signless Laplacian spectra of the corona and edge corona of two graphs［J］.Linear Multilinear A，2013，61（2）：197.

［23］ ASRATIAN A S，CASSELGREN C J.On interval edge colorings of （α，β）-biregular bipartite graphs［J］.Discrete Math，2007，307（15）：1951.

（責(zé)任編輯 馬宇鴻）