论文部分内容阅读
对图G的顶点和边进行着色，如果任意相邻顶点、相邻边以及相互关联的顶点和边都着不同颜色，则称此着色为图G的正常全着色.用颜色1,2,???, t对图G进行正常全着色，使得至少有一个顶点或一条边着色为i,i=1,2,…,t，并且对于每个顶点v∈ V(G)，与v关联的边以及v恰好着dG(v)+1个连续的颜色，则称此正常全着色为图G的t-区间全着色，这里dG(v)为顶点v在G中的度.对于正整数t，如果图G有一个t-区间全着色，则称图G为可t-区间全着色的.令ξt(t≥1)表示所有可t-区间全着色的图的集合，则ξ= Ut≥ξt表示所有可区间全着色的图的集合.对任意图G∈ξ，使得图G存在一个t-区间全着色的t的最小值和最大值分别记为ωT（G)和WT(G). 本文主要研究完全三部图K1,m,n和K2,m,n的区间全着色性.对于K1,m,n我们证明：对任意整数1≤m≤n，K1,m,n∈∈ξ且Wt(K1,m,n)=m+n+1;若m=1，则（此处为公式省略） 并且当Wt(K1,m,n)≤t≤Wt(K1,m,n)时，K1,m,n∈ξ；若 m>1，则m+n+4≤Wt（K1,m,n)≤ m+n+5，并且当 WT(K1,m,n)≤t≤m+n+4时，K1,m,n∈ξT. 对于K2,m,n我们证明：对任意整数m≥2，当n≥2 m时，K2,m,n∈ξT且Wt(K2,m,n)=m+n+1;对任意整数2≤m≤n，K2,m,n∈ξT且Wt（K2,m,n)≥ m+n+5. 最后给出了几类不可区间全着色的图.