T-型六角系统的邻点可区别I-全色数

杨随义

（天水师范学院 数学与统计学院，甘肃 天水 741001）

1 预备知识

图染色作为图论研究的重要方向之一，被广泛应用于信息计算科学、通信网络、交通运输等领域，为实际问题的解决提供了重要的理论依据和最优策略.图染色最早起源于四色问题的研究，随后一系列经典染色如点染色、边染色以及全染色等相继被提出.[1]点染色是若干种颜色在顶点（边）上的一个分配，且相邻顶点（边）分配不同的颜色，将所用的最少颜色数称为点（边）色数.图的全染色是若干种颜色同时在顶点和边上的一个分配，且满足相邻顶点与相邻边以及关联元素分配不同的颜色，类似地，将所用的最少颜色数称为全色数.1941年，Brooks证明任意一个既不是奇圈也不是完全图的连通图，其点色数不超过Δ.1964年前后，Vizing和Gupta分别独立证明了任意一个图的边色数不超过Δ+1.此外，Vizing还猜测：任意一个图的全色数不超过Δ+2，即后来众所周知的全染色猜想（TCC）.染色问题已被证明是一个NP-难问题，因此，为了进一步探索TCC猜想，国内外学者随后又相继提出了一系列可区别染色.2005年，张忠辅等[1]提出了图的邻点可区别全染色的概念，并给出了圈、完全图、完全二部图等一些特殊图类的邻点可区别全色数，并猜测图的邻点可区别全色数Δ+2.此后，国内外学者针对这一猜想展开了研究.[2，3]为了推动邻点可区别全色数猜想的研究，张忠辅等[4]在邻点可区别全染色的基础上，提出了邻点可区别I-全染色的概念.随后王继顺[4,5]研究了蛛网图、渔网图以及联图Pm∨Fn及Pm∨Wn[6]的邻点可区别I-全染色.张婷、赵慧霞等[7]给出了图C5∨Wn的邻点可区别I-全色数.

六角系统作为化学图论中重要的研究对象，受到了国内外学者的广泛关注.六角系统图是由正六边形所组成的平面图网络，其构型多种多样，不同的构型其化学性质也各不相同.T-型六角系统是一类特殊的六角系统，它是由一个正六边形中心分别向3个间隔方向延伸n个正六边形直链所构成的对称图，简称n阶T-型六角系统链.最近，王文杰等[8]首先研究了T-型六角系统链的点可区别边染色.本文以此为动机，研究了T-型六角系统Tn的邻点可区别I-全色数，并得到了其邻点可区别I-全色数.

定义1.1[1]设G是阶至少为2的连通图，k是正整数，f是V(G)⋃E(G)到{1,2,…,k}的映射，对任意u∈V(G)，记C(u)={f(u)}⋃{f(uv)|uv∈E(G),v∈V(G)}.如果

(1)对于任意uv,vw∈E(G),u≠w，有

f(uv)≠f(vw)；

(2)对于任意uv∈E(G),有

f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv)；

则称f为G的k-正常全染色，进一步，如果f还满足

2 主要结果