三角金字塔網的點、邊、全色數*

喻雪榮

(浙江師范大學數理與信息工程學院，浙江金華 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.