论文部分内容阅读
本文考虑的图无特别声明均为简单无向有限图．本文讨论了图的消染色和点染色的推广限制边的点染色．Pn为长度为n-1的路，Kn为具有n个端点的完全图，Kn,n表示完全二部图，G∨H表示图G和图H的并图，G=Km(n)表示一个完全m部图且每部分的顶点数均为n．
图G的消色数α(G)是指在图G的正常点染色中最大的颜色数满足顶点的任意俩个颜色类中至少有一条边相连.图G的伪染色是指在G的点染色中相邻的俩点可以染同色．图G的伪完全染色指在G的顶点的伪染色中，任意一对不同的颜色对在G中至少存在一条边其端点用这对颜色对着色.图G的伪消染色数Ψ(G)指图G的伪完全染色中使用的最多颜色数.图G的限制边的点染色是指对图G的顶点进行伪完全染色，使得任意一对染色对至少有k条边相连.Ψk(G)表示图G的限制边的染色数．当k=1时，限制边的点染色为图的伪消染色.本文主要证明了以下结论：
定理1对任意自然数t，t=2k+1，存在路Pn满足Ψ2(Pn)=2k+1，min|V(Pn)|=2k(2k+1)+1.
推论1对路Pn继续延长得到路P*满足|V(P*)|=mk(2k+1)+1，对延长的部分进行同样的着色，则路P*满足Ψm(P*)=2k+1．且路P*是满足Ψm(P)=2k+1的最短路，每对色类只出现m次，起末端点染同色．
定理2对自然数t,t=2k,存在路Pn满足Ψ2(Pn)=2k,min|V(Pn)|=2k(2k-1)+1．
推论2依次对P2k2延长染色，可得到路P满足Ψm(P)=2k,且min|V(P)|＝tA2k2+1,m=2t时，此时每对颜色类只出现m次，且起末端点染同色；min|V(P)＝(tA2k2+1)+(2k2-1)；m=2t+1时，此时每对颜色类出现m次或m+1次.
定理3即ψ2(Kn)＝[n-2],即n＝2k+1时，Ψ2(Kn)=k+1;n=2k时，Ψ2（Kn）=k.
定理4或者.
定理5或者.
定理6 G是最大度为△的简单图，且|V(G)|=p，则，n=Ψm(G)．
定理7 G=K3(n)(-个完全三部图且每部分的顶点数均为n)则．
定理8 G=Km(n)则．
定理9令3≤l1≤l2≤…≤lk是正整数且．如果,则Ψ（Cl1∪Cl2∪…∪ Clk）=Ψ(Cp)．
定理10对于绝大部分整数k，有Ψ(kC4)=Ψ(C4k).