论文部分内容阅读
给定整数k，d≥0以及一个图G=(V(G)，E(G))，如果用至多k种颜色就可以对它的所有边进行染色使得每条边至多可以和d条与它染同种颜色的边相邻则称图G是(k，d)﹡一边可染的.其中它的任意一个满足上述条件的边染色成为图G的一个(k，d)﹡一边染色的，且记d为G的边染色亏格数.记图G的非正常边染色数为Xd(G)=min{k｜图G是(k，d)﹡-边可染的).(K，0)﹡-边染色就是正常k边染色，并且X0(G)就是正常边染色数.
图的非正常染色是由Andrews，Jacobson[2]和F.Harary,K.Jones[19]以及L.J.Cowen，R.H.Cowen，D.R.Woodall[8]分别独立引入.已经知道每个平面图是(3，2)﹡-可染，每个外平面图都是(2，2)﹡-可染，不运用四色定理就能得到每个平面图是(4，1)﹡-可染[8].
本文从二部图结构入手利用非正常边染色定义得到结论：定理2.3x1ι(Kn,n)=n(n=1，2，3，4，5).定理2.4X1ι(Kn,n)=n-1(n=6，7，8).定理2.9 n为奇数或n=2时[(6n+2)2/8n+2]≤X1ι(K6n+2，6n+2)≤5n+2；
n为偶数时[(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)的一个(5n，1)﹡-边染色(或(5n+3，1)﹡-边染色)可以在O(n2)内找到定理2.22若n=(2m)·k+i(k≥1，0≤i≤2m-1)，则X1(Km，n)=mk+[i/2].
定理2.23 [3/4n]≤X1(Km,n)≤n(n+l)≤m≤2n-1)定理2.24X2(Kn,m)=[n/2]。
定理2.25如果n=t·r，则X2(r-1)(Kn,n)≤t