K3,4,p的点可区别一般全染色

杨佳睿, 陈祥恩

(西北师范大学 数学与统计学院, 甘肃 兰州 730070)

0 引 言

图的(邻)点可区别正常边染色、(邻)点可区别全染色及其相关猜想是受到当前国际著名图论专家(如Bollobás等)重视的研究课题.1985年,Harary等[1]建设性地提出点可区别一般边染色概念.1988年，Chartrand等[2]研究图的非正规强度，即图的可允许一般边染色所需要颜色的最少数目；1997年Burris等[3]及1996年Hork等[4-6]分别独立地提出图的点可区别正常边染色.Zagaglia[7]首次提出了点可区别的一般全染色概念.此后, 图的可区别染色成为运筹方向的热门领域，越来越多的学者投身其中，产出了许许多多相关成果.陈祥恩等[8-12]开辟了点可区别染色新方向，研究出许多新成果.点可区别的一般全染色是指满足(邻)点可区别及一般这两个概念的色集合对图的每个顶点的分配，其中，点可区别是指不同的点所分配的色集合均不相同，邻点可区别则是指相邻的点不能分配到相同的色集合.一般全染色是与正常全染色相对应的概念.正常全染色需满足三个条件，即相邻的点不能染相同的颜色(V-条件)，相邻的边不能染相同的颜色(E-条件)，以及关联的点与边不能染相同的颜色(I-条件).而一般全染色则不需要满足上述三个条件,在缺乏限制条件的情况下，色集合的分配也变得更加灵活和难以把握.事实上，图的点可区别的E-全染色(VDETC)、点可区别的IE-全染色(VDIETC)、点可区别的I-全染色(VDITC),以及邻点可区别的各种未必正常全染色，也是正在研究的课题.本文中出现了两个概念，gvt(G)定义为G的一般的点可区别全色数，k-GVDTC定义为图G的能够使用k种颜色的点可区别一般全染色.

K3,4,p的点可区别一般全染色已被证明,K3,4,p的一般的点可区别全色数已经给出.定义V=X∪Y∪Z为完全三部图Km,n,p的顶点集合, 其中,X={x1,x2,…,xm},Y={y1,y2,…,yn},Z={z1,z2,…,zp}，边集合为 {xiyj|i=1,2,…,m;j=1,2,…,n}∪{yjzt|j=1,2,…,n;t=1,2,…,p}∪{xizt|i=1,2,…,m;t=1,2,…,p}.

1 准备工作

证明首先利用反证法.假设K3,4,p有(l-1)-GVDTC.

反证法, 不妨设Z中包含{3},{4},…,{l-1}, 1-子集中仅仅不含{1},{2}这两个集合,那么C(xi)∩C(yj)⊇{3,4,…,l-1}, 由于点染色满足可区别性, 则只有{3,4,…,l-1}, {1,3,4,…,l-1}, {2,3,4,…,l-1}和 {1,2,3,4,…,l-1}这 4 个集可以分配给X∪Y中的7 个顶点, 显然矛盾.

表1与表2给出K3,4,p的一个l-GVDTCf.

表1 K3,4,p的点染色方案

表2 K3,4,p的边染色方案

因∀v∈V(K3,4,p), 均有C(v)=D(v).故得到K3,4,p的l色的点可区别一般全染色.

2 主要结果及其证明

定理1

证明按照从一般到特殊分情形讨论:

证明在引理 1、引理 2中已给出证明.

情形2当 499≤p≤1 006 时,gvt(K3,4,p)=10.

证明假设K3,4,p有 9-GVDTC.

断言3 当499≤p≤1 006,∀v∈X∪Y,|C(v)|≥6.

断言4当499≤p≤1 006,Z的色集合中至多含有6个 1-子集.

反证法, 不妨设Z中包含{3},{4},…,{9}, 1-子集中仅仅不含{1},{2}这两个集合,那么C(xi)∩C(yj)⊇{3,4,…,9}, 由于点染色满足可区别性, 则只有{3,4,…,9}, {1,3,4,…,9}, {2,3,4,…,9}和 {1,2,3,4,…,9}这 4 个集合可以分配给X∪Y中的7 个顶点, 显然矛盾.

下面阐述K3,4,1 006的 10-GVDTC染色方案,先分配{1,2,3,4,…,10} 的子集给K3,4,p的每个顶点, 令D(x1)={1,2,…,10},D(x2)=D(x1){1},D(x3)=D(x1){2},D(y1)=D(x1){3},D(y2)=D(x1){4},D(y3)=D(x1){5},D(y4)=D(x1){6},将除{1},{2},{3},{4},{5},{6}外的 {1,2,…,10}的其余子集作为Z中点的色集合,详细的边染色与点染色方案可参照表1与表2所述给出.

情形3当243≤p≤498 时,gvt(K3,4,p)=9.

证明：假设K3,4,p有 8-GVDTC.

断言5 当243≤p≤498,K3,4,p的∀v∈X∪Y,|C(v)|≥5.

断言6 当243≤p≤498,Z的色集合中至多含有5个 1-子集.

反证法, 不妨设Z中包含{3},{4},…,{8}, 1-子集中仅仅不含{1},{2}这两个集合,那么C(xi)∩C(yj)⊇{3,4,…,8}, 由于点染色满足可区别性, 则只有{3,4,…,8}, {1,3,4,…,8}, {2,3,4,…,8}和 {1,2,3,4,…,8}这 4 个集合可以分配给X∪Y中的7 个顶点, 显然矛盾.

下面阐述K3,4,498的 9-GVDTC染色方案,先分配{1,2,3,…,9}的子集给K3,4,p的每个顶点, 令D(x1)={1,2,…,9},D(x2)=D(x1){1},D(x3)=D(x1){2},D(y1)=D(x1){3},D(y2)=D(x1){4},D(y3)=D(x1){5},D(y4)=D(x1){6},将除{1},{2},{3},{4},{5},{6}外的 {1,2,…,9}的其余子集作为Z中点的色集合,详细的边染色与点染色方案可参照表1与表2所述给出.

情形4当 115≤p≤242 时,gvt(K3,4,p)=8.

证明假设K3,4,p有 7-GVDTC.

断言7当 115≤p≤242,∀v∈X∪Y,|C(v)|≥4.

断言8当 115≤p≤242,Z的色集合中至多含有4个 1-子集.

反证法, 不妨设Z中包含{3},{4},…,{7}, 1-子集中仅仅不含{1},{2}这两个集合,那么C(xi)∩C(yj)⊇{3,4,…,7}, 由于点染色满足可区别性, 则只有{3,4,…,7}, {1,3,4,…,7}, {2,3,4,…,7}和 {1,2,3,4,…,7}这 4 个集合可以分配给X∪Y中的7 个顶点, 显然矛盾.

K3,4,242的 8-GVDTC的详细边染色与点染色方案可参照表1与表2所述给出.

情形5当 51≤p≤114 时,gvt(K3,4,p)=7.

证明假设K3,4,p有 6-GVDTC.

断言9当 51≤p≤114,∀v∈X∪Y,|C(v)|≥3.

断言10当 51≤p≤114,Z的色集合至多含有3个 1-子集.

反证法, 不妨设Z中包含{3,4,5,6}, 1-子集中仅仅不含{1},{2}这两个集合,那么C(xi)∩C(yj)⊇{3,4,5,6}, 由于点染色满足可区别性,则只有{3,4,5,6}, {1,3,4,5,6}, {2,3,4,5,6}和{1,2,3,4,5,6}这 4 个集合可以分配给X∪Y中的7 个顶点, 显然矛盾.

K3,4,114的 7-GVDTC的详细边染色与点染色方案可参照表1与表2所述给出.

情形6当 19≤p≤50 时,gvt(K3,4,p)=6.

证明假设K3,4,p有 5-GVDTC.

断言11当 19≤p≤50,∀v∈X∪Y,|C(v)|≥3.

断言12当 19≤p≤50,Z的色集合至多含有2个 1-子集.

反证法, 不妨设Z中包含{3,4,5}, 1-子集中仅仅不含{1},{2}这两个集合,那么C(xi)∩C(yj)⊇{3,4,5}, 由于点染色满足可区别性, 则只有{3,4,5}, {1,3,4,5}, {2,3,4,5}和{1,2,3,4,5}这 4 个集合可以分配给X∪Y中的7 个顶点, 显然矛盾.

K3,4,50的 6-GVDTC的详细边染色与点染色方案可参照表1与表2所述给出.

情形7当 5≤p≤18 时,gvt(K3,4,p)=5.

证明假设K3,4,p有 4-GVDTC.

断言13当 5≤p≤18,X的色集合中不含1-子集.

断言14当 5≤p≤18,Y的色集合中不含1-子集.

断言15当 5≤p≤18,Z的色集合中至多含有1个 1-子集.

反证法, 不妨设Z中含有{3},{4},仅不含 {1},{2} 这两个色集合,即C(xi)∩C(yj)⊇{3,4}, 由于点染色满足可区别性, 则只有{3,4}, {1,3,4}, {2,3,4}和{1,2,3,4}这 4 个集合可以分配给X∪Y中的7 个顶点, 显然矛盾.

K3,4,18的 5-GVDTC的详细边染色与点染色方案可参照表1与表2所述给出.

情形8当p=4 时,gvt(K3,4,p)=4.

证明假如K3,4,4有 3-GVDTC.使用的 3 种颜色为 1,2,3.那么可分配的色集合有 7 个,无法区分X∪Y∪Z中的至少 11 个顶点, 矛盾.此时，K3,4,4没有 3-GVDTC.在表3中给出了K3,4,4的4-GVDTC.

表3 K3,4,4的全染色方案