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

黃大江,何文杰

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

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

黃大江,何文杰

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

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

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

猜想1(均勻染色猜想)對于除了完全圖和奇圈的任何一個連通圖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′)是任意兩個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是一條路長為|Pm|=m+1的路,Qd是一個超立方體,Kk,m是完全二分圖。

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

定理1.6[3]令G=G(X,Y)是一個連通二分圖。如果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)的中心點,用a1,a2,…,am(b1,b2,…,bn)標(biāo)記G1(G2)的其他點,用a0b0,a0b1,…,a0bn, a1b0,a1b1,…,a1bn,…,am b0,…,am bn來標(biāo)記K1,m□K1,n中的點.按照以下來排列這(m+1)(n+1)個點。

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

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

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

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

[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

國家自然科學(xué)基金資助項目(10871058)

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