三角金字塔网的点、边、全色数*

喻雪荣

(浙江师范大学数理与信息工程学院，浙江金华 321004)

0 引 言

本文所考虑的图均为有限简单的无向图.对于图G，分别用V(G)，E(G)和Δ(G)表示图G的顶点集、边集和最大度.图染色的基本问题就是确定各种染色法的色数，目前已有许多研究结果［1-6］.

图G的正常k-染色是指一个映射f:V(G)→{1，2，…，k}，满足∀uv∈E(G)，f(u)≠f(v);若G有一个正常k-染色，则称图G是k-可染的;色数χ(G)是指使得图G是k-可染的最小整数k;图G的正常k-边染色是从边集E(G)到颜色集合{1，2，…，k}的一个映射，使得相邻的边染不同的颜色;边色数χ'(G)是指使得图G是k-边可染的最小整数k;图G的k-全染色是用k种颜色对图G的V(G)∪E(G)中的元素进行染色，使得相邻或者相关联的两元素染不同的颜色.全色数χT(G)是指使得图G存在k-全染色的最小整数 k.显然，Δ(G)+1≤χT(G).

三角金字塔网TPL是由Razivi和Sarbazi-Azad在三角格网Tn的基础上提出来的一个分层网络.文献［7］给出了TPL的色数的上界，即χ(TPL)≤6.本文确定了TPL的点色数χ(TPL)、边色数χ'(TPL)和全色数χT(TPL).

1 三角金字塔网

首先介绍一下三角格网Tn的定义.

定义1 用Tn表示层数为n的三角格网，其顶点集为 V(Tn)={(x，y)|0≤x+y≤n}，Tn中的2 个点(x1，y1)和(x2，y2)相邻当且仅当|x1-x2|+|y1-y2|=1，或 x2=x1+1 且y2=y1-1，或 x2=x1-1 且 y2=y1+1.

图1为4层三角格网T4.

定义2 用TPL表示L层三角金字塔网，其顶点集为 V(TPL)={(k，x，y)|0≤k≤L，0≤x+y≤k}.点(k，x，y)表示第 k层坐标为(x，y)的点.k 层的点集构成一个三角格网 Tk，k 层的点(k，x，y)与k+1层的点(k+1，x，y)，(k+1，x+1，y)和(k+1，x，y+1)相邻.

图1 4层三角格网T4

图2为4层三角金字塔网TP4.

图G中顶点v所关联的边的数目称为顶点v的度，记为dG(v)或d(v).

由TPL的定义知，TPL中的点度有3，6，9 或 12，当且仅当 L≥4 时，Δ(TPL)=12.若点u的顶点度为12，则它的邻点集为 N(u)={(k-1，x-1，y)，(k-1，x，y)，(k-1，x，y-1)，(k，x-1，y)，(k，x-1，y+1)，(k，x，y-1)，(k，x，y+1)，(k，x+1，y-1)，(k，x+1，y)，(k+1，x，y)，(k+1，x，y+1)，(k+1，x+1，y)}.TPL的点数和边数分别为(L+2).

图2 4层三角金字塔网TP4

2 主要结果

定理1 当L≥1时，TPL的色数是χ(TPL)=4.

证明 当L≥1时，因为TPL含有完全子图K4，所以χ(TPL)≥χ(K4)=4.

下证χ(TPL)≤4.根据点的每个分量的奇偶性将TPL的顶点集合V(TPL)分成4个集合，V1={(偶，偶，偶)，(奇，奇，奇)}，V2={(偶，偶，奇)，(奇，奇，偶)}，V3={(偶，奇，偶)，(奇，偶，奇)}，V4={(奇，偶，偶)，(偶，奇，奇)}.由TPL的定义知，图TPL中的任意一个点u与它的邻点至少有1个分量的奇偶性相同，故 Vi(i=1，2，3，4)是独立集.将 Vi(i=1，2，3，4)中的点染颜色 i，则任意2 个相邻的点染不同的颜色，所以χ(TPL)≤4.定理1证毕.

定理2 当L≥4时，TPL的边色数是χ'(TPL)=12.

证明 当L≥4时，Δ(TPL)=12，故有 χ'(TPL)≥12.

下证χ'(TPL)≤12.只须给出TPL的一个正常12-边染色即可.可以将TPL看成是由6个不同方向的多条路组成的图.设点v的点度为12，与v相关联的边集分成6个不同方向:

在li(i∈{1，2，…，6})方向上的边交错染颜色2i-1和2i.对TPL中任意点u，与它相关联的所有边都在上述6个方向上，并且不同方向的边染不同颜色，在同一个方向上的2条边也染不同的颜色.所以，χ'(TPL)≤12.定理2证毕.

定理3 当L≥4时，TPL的全色数是χT(TPL)=13.

证明 当L≥4时，Δ(TPL)=12，故有 χT(TPL)≥Δ(TPL)+1=13.

下证χT(TPL)≤13.只须给出TPL的一个正常13-全染色即可.

首先根据定理1的染色规则，给TPL的顶点染4种颜色{1，2，3，4}，并记4种颜色的点集分别为V1，V2，V3，V4.根据 TPL的定义和定理 2，在 k 层上的边共有 3 个方向 l3，l4，l5，再用 6 种颜色{5，6，7，8，9，10}，根据定理2的染色规则，给TPL在k(1≤k≤L)层上的边进行染色.

用E1表示k(k为奇数)层与k+1层之间的边集，用E2表示k(k为偶数)层与k+1层之间的边集，用 E1［Vi，Vj］表示 k(k为奇数)层染颜色i的点与 k+1层染颜色 j的点之间的边集，用 E2［Vi，Vj］表示k(k为偶数)层染颜色i的点与k+1层染颜色j的点之间的边集.

用4 种颜色{1，2，3，4}来染 E1中的边.若 e∈E1［V2，V3］∪E1［V3，V4］∪E1［V4，V2］，则将边 e染颜色 1;若 e∈E1［V1，V4］∪E1［V3，V1］∪E1［V4，V3］，则染颜色 2;若 e∈E1［V1，V2］∪E1［V2，V4］∪E1［V4，V1］，则染颜色 3;若 e∈E1［V1，V3］∪E1［V2，V1］∪E1［V3，V2］，则染颜色 4.

用 3 种颜色{11，12，13}来染 E2中的边.若 e∈E2［V1，V2］∪E2［V2，V4］∪E2［V3，V1］∪E2［V4，V3］，则将边 e染颜色 11;若 e∈E2［V1，V3］∪E2［V2，V1］∪E2［V3，V4］∪E2［V4，V2］，则染颜色 12;若 e∈E2［V1，V4］∪E2［V2，V3］∪E2［V3，V2］∪E2［V4，V1］，则染颜色 13.

根据定理1，任意相邻两点都染不同颜色，由给出的边的染色规则，易验证任意相邻两边或相关联的点和边都染不同的颜色.定理3证毕.

［1］Jakovac M，Klavžar S.Vertex-，edge-，and total-colorings ofgraphs［J］.Discrete Mathematics，2009，309(6):1548-1556.

［2］Chen Meirun，Guo Xiaofeng.Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes［J］.Information Processing Letters，2009，109(12):599-602.

［3］Liu Bin，Hou Jianfeng，Wu Jianliang，et al.Total colorings and list total colorings of planar graphs without intersecting 4-cycles［J］.Discrete Mathematics，2009，309(20):6035-6043.

［4］薛玲，吴建良.较少短圈的平面图的全色数［J］.山东大学学报:理学版，2012，47(9):84-87.

［5］王侃.最大度为6的平面图是13-线性可染的［J］.浙江师范大学学报:自然科学版，2012，35(2):121-124.

［6］傅彩霞.若干倍图的均匀染色［J］.浙江师范大学学报:自然科学版，2012，35(2):133-137.

［7］Razavi S，Sarbazi-Azad H.The triangular pyramid:routing and topological properties［J］.Information Sciences，2010，180(11):2328-2339.