二部圖的非正常邊染色.pdf

1、給定整數(shù)k，d≥0以及一個圖G=(V(G)，E(G))，如果用至多k種顏色就可以對它的所有邊進行染色使得每條邊至多可以和d條與它染同種顏色的邊相鄰則稱圖G是(k，d)﹡一邊可染的.其中它的任意一個滿足上述條件的邊染色成為圖G的一個(k，d)﹡一邊染色的，且記d為G的邊染色虧格數(shù).記圖G的非正常邊染色數(shù)為Xd'(G)=min{k｜圖G是(k，d)﹡-邊可染的).(K，0)﹡-邊染色就是正常k邊染色，并且X'0(G)就是正常邊染色數(shù).

2、 圖的非正常染色是由Andrews，Jacobson[2]和F.Harary,K.Jones[19]以及L.J.Cowen，R.H.Cowen，D.R.Woodall[8]分別獨立引入.已經(jīng)知道每個平面圖是(3，2)﹡-可染，每個外平面圖都是(2，2)﹡-可染，不運用四色定理就能得到每個平面圖是(4，1)﹡-可染[8]. 本文從二部圖結(jié)構(gòu)入手利用非正常邊染色定義得到結(jié)論：定理2.3x1ι(Kn,n)=n(n=1，2，3，4，5

3、).定理2.4X1ι(Kn,n)=n-1(n=6，7，8).定理2.9 n為奇數(shù)或n=2時[(6n+2)2/8n+2]≤X1ι(K6n+2，6n+2)≤5n+2； n為偶數(shù)時[(6n+2)/8n+2]≤X1'(K6n+2,6n+2)≤5n+3(n≥4).定理2.12 [(6n+i)2/8n+i+i/3]≤X1ι(K6n+i,6n+i)≤5n+i(i=0，1，3，4，5；n≥1)定理2.7K6n,6n(或K6n+3,6n+3)的一