黃大江,何文杰

(河北工業(yè)大學(xué)理學(xué)院應(yīng)用數(shù)學(xué)研究所,天津 300130)

K1,m□K1,n的均勻染色

黃大江,何文杰

(河北工業(yè)大學(xué)理學(xué)院應(yīng)用數(shù)學(xué)研究所,天津 300130)

一個(gè)圖G可均勻k-染色,如果它的點(diǎn)集可分為k個(gè)獨(dú)立集合,使得每?jī)蓚€(gè)不同集合中點(diǎn)的數(shù)目最多差1。使這種染色存在的最小數(shù)k稱為圖G的均勻染色數(shù),記作x=(G)。在本文中,得到了關(guān)于圖K1,m□K1,n的均勻染色結(jié)果,2≤x=(K1,m□K1,n)≤4。

星圖;均勻染色;笛卡爾積

1 引言

令G=(V(G),E(G))是一個(gè)簡(jiǎn)單圖,用V(G)和E(G)分別表示G的頂點(diǎn)集和邊集。G中的一個(gè)元素是G的一個(gè)點(diǎn)或一條邊。邊{u,v}記作uv或vu。兩個(gè)圖G1=(V1,E1)和G2=(V2,E2)的笛卡爾積G1□G2是這樣一個(gè)圖,它的點(diǎn)集是V1×V2,點(diǎn)(a,b)與點(diǎn)(c,d)相鄰接當(dāng)且僅當(dāng)a=c且b與d相鄰接,或者b=d且a與c相鄰接。一個(gè)圖G被稱作是均勻k-可染的,如果它的點(diǎn)集可分為k個(gè)類V1,V2,…, Vk,使得每一個(gè)V i都是獨(dú)立集,且滿足‖V i|-|V j‖≤1其中1≤i,j≤k。滿足上述條件的最小的數(shù)k被稱為圖G的均勻染色數(shù),記作x=(G)。

1973年,M eyer[5]提出了下面的猜想。

猜想1(均勻染色猜想)對(duì)于除了完全圖和奇圈的任何一個(gè)連通圖G,都有x=(G)≤Δ(G)。這里有關(guān)于一些圖笛卡爾積的均勻染色結(jié)果:

定理1.1[2]如果G1和G2都是均勻k-可染的,那么G1□G2也是均勻k-可染的。

定理1.2[2]

定理1.3[2]令G1(V1,V2,…,V r)和G2(V1′,V2′,…,V r′)是任意兩個(gè)r-剖分圖,使得|V1|′=|V2|′=…=|V r|′成立,那么有x=(G1□G2)≤r。

定理1.4[2]令k,m,n和r都是正整數(shù)。那么以下圖的均勻染色數(shù)都等于2。G2m□G2n,Pm□Pn, Qr□G2n,Kk,m□G2n,K1,m□G2n,Pm□P2n,Qr□P2n,Kk,m□P2n,K1,m□P2n,QrQr,其中Pm是一條路長(zhǎng)為|Pm|=m+1的路,Qd是一個(gè)超立方體,Kk,m是完全二分圖。

定理1.5[1]令G1為具有n個(gè)點(diǎn)的圖,G2是n-可染的。那么G1□G2是均勻n-可染的。

定理1.6[3]令G=G(X,Y)是一個(gè)連通二分圖。如果G不同于任何一個(gè)完全二分圖Kn,n,那么G可以被Δ(G)種顏色均勻染色。

定理1.7[4]假設(shè)pi是正整數(shù)且M是滿足pi(modM)<「pi/M┒其中i=1,…,n的最大整數(shù)。那

2 K1,m□K1,n的均勻染色

現(xiàn)在令m,n都為正整數(shù),不失一般性,可以假設(shè)m≤n,考慮星圖G1=K1,m和G2=K1,n,我們用a0(b0)標(biāo)記G1(G2)的中心點(diǎn),用a1,a2,…,am(b1,b2,…,bn)標(biāo)記G1(G2)的其他點(diǎn),用a0b0,a0b1,…,a0bn, a1b0,a1b1,…,a1bn,…,am b0,…,am bn來(lái)標(biāo)記K1,m□K1,n中的點(diǎn).按照以下來(lái)排列這(m+1)(n+1)個(gè)點(diǎn)。

如果m=2k+1,n=2l+1,其中k,l均為正整數(shù),那么把圖K1,m□K1,n中的(m+1)(n+1)個(gè)點(diǎn)分成16個(gè)區(qū)域,其中每一個(gè)區(qū)域都是由相互獨(dú)立的點(diǎn)組成的。

用0,1,2,3來(lái)染這些點(diǎn)并且把它們標(biāo)記在相應(yīng)的區(qū)域。易見這是一個(gè)正常染色,并且染了0,1,2,3的點(diǎn)的數(shù)目分別為:

那么,從區(qū)域D任選┖(k-1)/2」個(gè)點(diǎn),把它們的顏色從1變?yōu)?;從區(qū)域B任選┖(k-1)/2」個(gè)點(diǎn),把它們的顏色從3變?yōu)?;從區(qū)域A任選┖(k-1)/2」個(gè)點(diǎn),把它們的顏色從0變?yōu)?;完成這些操作之后,染了同種顏色的點(diǎn)仍然都相互獨(dú)立并且

接下來(lái),從區(qū)域D任選┖(l+k)/2」個(gè)點(diǎn),把它們的顏色從1變?yōu)?;從區(qū)域C任選┖(l-k)/2」個(gè)點(diǎn),把它們的顏色從2變?yōu)?;從區(qū)域A任選┖(l-k)/2」個(gè)點(diǎn),把它們的顏色從0變?yōu)?;完成這些操作之后,染了同種顏色的點(diǎn)仍然都相互獨(dú)立并且

[1] Bor-Liang Chen,Ko-Wei Lih.Equitable Coloring of Interval Graphs and Products of Graphs,arX-iv:0903.1396v1[math. CO],2009.

[2] Hanna Furmańcyzk,EQU IT ABL E COLORING OF GRA PH PRODU CTS some,Opuscula M athe matica.Vol 26(2006)No.1.

[3] Peter Che Bo r Lam,Wai Chee Shiu,On the equitable chromatic number of com p lete n-partite graphs[J].Discrete App lied M athematics.2001,113:307-310.

[4] Ko-Wei Lih,Pou-Lin WuOn equitable coloring of bipartite graphs[J].Discrete Mathematics.1996,151:155-160.

[5] W.MeyerEquitable coloring,Amer.Math.Monthly.1973,80:920-922.

Equitable coloring of K1,m□K1,n

HUANGDa-jiang,HEWen-jie

(A pplied M athematics Institute,Hebei University of Technology,Tianjin300401,China)

A graph G is equitablyk-colorable if its vertices can be partitioned intokindependent sets in such a way that the number of vertices in any two sets differs by atmost one.The smallestkfor w hich such a colo ring exists is know n as the equitable chromatic num ber ofGand deno tedX=(G).In this paper,we obtain result on equitable coloring ofK1,m□K1,n.2≤x=(K1,m□K1,n)≤4.

Star graph;Equitable colo ring;Cartesian p roduct

O157

:A

1001-9383(2011)01-0001-05

2010-09-12

國(guó)家自然科學(xué)基金資助項(xiàng)目(10871058)

黃大江(1985-),男,河北邢臺(tái)人,碩士研究生,從事圖的染色問題的研究.