Vertex Distinguishing Proper Edge Coloring of T-Shaped Hexagonal Systems

p(p≥1)阶T-型六角系统H是由2度点和3度点组成的，其中n₂=6p+6，n₃=6p.它的边组合度为

由于当θ≥5时，$\left( \begin{array}{l} \theta \\ 3 \end{array} \right) \ge \left( \begin{array}{l} \theta \\ 2 \end{array} \right) $，而对p≥1，都有θ≥5成立，因此

此时$ \pi \left( H \right) = k \cdot \left\lceil {\frac{{1 + \sqrt {48p + 49} }}{2}} \right\rceil . $

接下来将给出一个染色的算法，对p(p≥4)阶T-型六角系统H的所有2度点相关联的边进行着色，直到没有边剩余.

首先把$ \left( \begin{array}{l} k\\ 2 \end{array} \right) $种2色集合按顺序排列出来，如图 1.

根据图 1中色集合的排列，得到如下染色序列，并记c(i)为上述序列中第i个位置所对应的颜色：

1，2，1，3，1，4，1，5，1，6，1，7，1，8，…，1，k-1，1，k；

2，3，2，4，2，5，2，6，2，7，2，8，…2，k-1，2，k；

3，4，3，5，3，6，3，7，3，8，…，3，k-1，3，k；

4，5，4，6，4，7，4，8，…，4，k-1，4，k；

…

k-1，k.

其次，将H的各个分支按逆时针方向标记为H₁，H₂，H₃，将中心六边形的各顶点按逆时针方向依次标记为w₁，w₂，w₃，w₄，w₅，w₆，再分别对各分支的顶点进行标号，如图 2，其中t=2p-2.

算法1

输入：p(p≥10)阶T-型六角系统H.

输出：关于H的所有2度点可区别k+1边着色.

步骤1  把u_2tl₂₁l₂₂l₂₃l₂₄v_2t依次赋予颜色2，3，4，5，1；把u_3tl₃₁l₃₂l₃₃l₃₄v_3t依次赋予颜色1，4，2，5，3.

步骤2  去掉图 1中前4列的10个2色集合{1，2}，{1，3}，{1，4}，{1，5}，{2，3}，{2，4}，{2，5}，{3，4}，{3，5}，{4，5}之后，再重新排序，得到新序列如下：

1，6，1，7，1，8，…，1，k-1，1，k；

2，6，2，7，2，8，…2，k-1，2，k；

3，6，3，7，3，8，…，3，k-1，3，k；

4，6，4，7，4，8，…，4，k-1，4，k；

…

5，6，5，7，5，8，…，5，k-1，5，k；

6，7，6，8，6，k-1，6，k；

7，8，7，k-1，7，k，…，k-1，k.

容易看出对任意i均满足c(i)≠c(i+1).当i是偶数时，c(i)≥6，c(i)＞c(i-1)，c(i)≠c(i+2)；当i是奇数时，c(i)是递增函数.

步骤3  令i=1.

步骤 4  令P₍₁₎=w₁u₁₁u₁₂u₁₃u₁₄…u_1t-1u_1tl₁₁l₁₂，P₍₂₎=l₁₃l₁₄v_1tv_1t-1…v₁₄v₁₃v₁₂v₁₁w₂，P₍₃₎=w₃u₂₁u₂₂u₂₃u₂₄…u_2t-1u_2t，P₍₄₎=v_2tv_2t-1…v₂₄v₂₃v₂₂v₂₁w₄，P₍₅₎=w₅u₃₁u₃₂u₃₃u₃₄…u_3t-1u_3t，P₍₆₎=v_3tv_3t-1…v₃₄v₃₃v₃₂v₃₁w₆.此时对路P₍₁₎，P₍₂₎，P₍₃₎，P₍₄₎，P₍₅₎，P₍₆₎进行边着色.记u为路P_(i)(i=1，…，6)中的任意点，u′为点u的后继顶点.令u=w₁，则u′=u₁₁.把边uu′染以c(i)色，此时令u=u′，i=i+1.

步骤5  若u=l₁₂，则说明路P₍₁₎被染完，执行.

令u=l₁₃，u′=l₁₄.将边uu′染以c(i)色.此时令u=u′，i=i+1.

若u=w₂，则说明路P₍₂₎被染完，执行.

令u=w₃，u′=u₂₁.将边uu′染以c(i)色.此时令u=u′，i=i+1.

若u=u_2t，则说明路P₍₃₎被染完，执行.

令u=v_2t，u′=v_2t-1.将边uu′染以c(i)色.此时令u=u′，i=i+1.

若u=w₄，则说明路P₍₄₎被染完，执行.

令u=w₅，u′=u₃₁.将边uu′染以c(i)色.此时令u=u′，i=i+1.

若u=u_3t，则说明路P₍₅₎被染完，执行.

令u=v_3t，u′=v_3t-1.将边uu′染以c(i)色.此时令u=u′，i=i+1.

若u=w₆，则说明路P₍₆₎被染完.

结束.

步骤6  引入新色k+1，将边l₁₂l₁₃染以k+1色.

通过上述算法1，能够得到一个关于T-型六角系统H的所有2度点的点可区别(k+1)-边染色.将w₁w₂w₃w₄w₅w₆w₁依次赋予颜色4，1，2，3，2，5.此时对于T-型六角系统H，只有边u_i2v_i2，u_i4v_i4，…，u_it-2v_it-2，u_itv_it(i=1，2，3)没有被染色，又因这些边互不相交，所以可以用新色k+1对其同时进行着色.

下面对3度点w_i(i=1，…，6)进行分析，可设C(w₁)={4，5，a}，C(w₂)={1，4，b}，C(w₃)={1，2，d}，C(w₄)={2，3，f}，C(w₅)={2，3，g}，C(w₆)={2，5，h}.由于染色算法的顺序性且路P_i(i=1，…，6)均为偶数阶，则b≠d，f≠g，且a=1；b，f，h≥6；d≥3；g≥4.否则，分别有：

成立，即分别有：

此时，分别有$ k < \frac{{15 + \sqrt {57} }}{2} $，k＜9.不符合题意.于是点w_i是正常边染色且色集合均可区分.又因点w_i(i=1，…，6)的色集合不含k+1色，于是点w_i与其他3度点均可区分.

上述染色算法对任意的u_ij，v_ij(i=1，2，3；j=2，4，6，…，t-2，t)均满足C(u_ij)≠C(v_ij)，且除了点u_2t，v_2t，u_3t，v_3t外，其他点的色集合均可互相区别.

下面考虑u_2t，v_2t，u_3t，v_3t这4个三度点的色集合，对u_2tv_2t，u_3tv_3t两条边进行调色.

分别设边v_3t-2v_3t-1，v_3t-1v_3t，u_3t-1u_3t，v_2t-2v_2t-1，v_2t-1v_2t，u_2t-1u_2t上的颜色依次为：x₁，x₂，x₃，y₁，y₂，y₃.由于x₁≠x₂，x₁≠x₃且x₁≥6，于是可以用颜色x₁对u_3tv_3t正常染色，此时点v_3t的色集合为{3，x₁，x₂}，u_3t的色集合为{1，x₁，x₃}，又由于x₂≥4，x₃≥6，于是除了点u_2t，v_2t外均可区别.同理可以用颜色y₁对u_2tv_2t正常染色，此时点v_2t的色集合为{1，y₁，y₂}，u_2t的色集合为{2，y₁，y₃}，其中y₁，y₃≥6，y₂≥3.容易看出，u_2t的色集合与其他点的均可区分，而点v_2t的色集合有可能与点u_3t或点w₂的区分不开.根据染色序列的性质能够得到x₁，x₃＞y₂，于是点v_2t的色集合与点u_3t的一定可区别.若点v_2t的色集合与点w₂的相同，此时取颜色c≥6且不同于b，y₂，y₃即可.又由于p≥10，于是χ_vd′(H)≥π(H)=12，因此颜色c的取法至少有4种可以对边u_2tv_2t正常着色.

至此，就用算法1得到了p(p≥10)阶T-型六角系统H的(k+1)-点可区别边染色.

当4≤p≤9时，k=π(H)，于是9≤k≤12，其算法与算法1类似，这里不再赘述，只需调整部分颜色，并将w₁w₂w₃w₄w₅w₆w₁依次赋予颜色2，5，4，2，3，4.此时d≤3.若d≥4，则

于是求得k≤5或k≥16，矛盾.

定理1  对p(p≥1)阶T-型六角系统H，均有

证  由于

求得

于是

首先，分别给出p=1，2，3时的p阶六角系统H的点可区别边染色，如图 3.

p=1时，π(H)=6，χ_vd′(H)=6；

p=2时，π(H)=7，χ_vd′(H)=7；

p=3时，π(H)=8，χ_vd′(H)=8.

因此当p=1，2，3时，满足题意

当p≥4时，由算法1可得

至此，就得到了p(p≥1)阶T-型六角系统H的(k+1)-点可区别边染色，它的点可区别边色数满足

于是定理1得证.因此p(p≥1)阶T-型六角系统H的点可区别边染色符合文献[6]中的猜想.