齒輪圖的鄰點強可區別的全染色

張東翰，李 超

(商洛學院數學與計算機應用學院，726000，陜西，商洛)

齒輪圖的鄰點強可區別的全染色

張東翰，李 超

(商洛學院數學與計算機應用學院，726000，陜西，商洛)

齒輪圖；鄰點強可區別的全染色；鄰點強可區別的全色數

0 引言

1 預備知識

定義1[7]：設G(V,E)是階數不小于3的簡單連通圖，k是自然數，f是從V(G)∪E(G)到{1,2…k}的映射，如果滿足：

1)對任意的邊uv∈E(G),f(u)≠f(v),f(u)≠f(uv)≠f(v)；

2)對任意的兩相鄰的邊uv,uw∈E(G)(v≠w),f(uv)≠f(uw)；

3)對任意的邊uv∈E(G)，其端點的色集合滿足C(u)≠C(v)，其中任一頂點u的色集合為C(u)={f(u)}∪{f(v)|uv∈E(G)}∪{f(uv)|uv∈E(G)}。

則稱f是圖G的一個鄰點強可區別的全染色法(簡記作k-AVSDTC)，且稱數χast(G)=min{k|G存在k-AVSDTC}為G的鄰點強可區別的全色數。

引理1[7]：設圖G是階數不小于3的圖，有χast(G)≥△+1；若G有相鄰的2個最大度點，則有χast(G)≥△+2，其中△代表圖G的最大度。

本文中未加敘述的術語、記號可在文獻[9-11]中找到。

2 定理及其證明

綜上可知，定理2成立。

[1]Zhang Zhongfu,Zhang Jianxun,Wang Jianfang,The total chromatic number of some graphs[J].Science Sinica Ser A:1434-1441.

[2]張東翰.蛛形圖的全染色和星全染色[J].商洛學院學報,2013,27(6):31-32.

[3]李曉東.圖全染色的幾個定理[J].哈爾濱理工大學學報,2001,6(1):100-102.

[4]張忠輔,陳祥恩,李敬文,等.關于圖的鄰點可區別的全染色[J].中國科學:A輯,2004,35(5):574-583.

[5]張東翰,王曉.路的廣義Mycielski圖的鄰點可區別的全染色[J].蘭州理工大學學報,2009,35(5):146-147.

[6]陳祥恩,張忠輔.Pm∨Pn的鄰點可區別的全染色[J].西北師范大學學報,2005,41(1):13-15.

[7]張忠輔,程輝,姚兵.圖的鄰點強可區別的全染色[J].中國科學:A輯,2007,37(9):1073-1082.

[9]張東翰,朱白.路的D(3)-點可區別的全染色[J].商

洛學院學報,2014,28(2):11-12.

[10]Bondy J A,Murty U S R.Graph Theory with Applications[M].New York:The Macmillan Press Ltd,1976.

[11]Reinhard D.Graph Theory[M].New York:Springer-Verlag,1997.

TheAdjacent-Vertex-Strongly-DistinguishingTotalColouringoftheGearGraph

ZHANG Donghan,LI Chao

(College of Mathematics and Computer Applications,Shangluo University,726000,Shangluo,Shanxi,PRC)

the gear graph;the adjacent vertex strongly distinguishing total colouring;the adjacent vertex strongly distinguishing total chromatic number

2014-05-21;

2014-06-23

張東翰(1981-)，男，河北邢臺人，碩士，講師，研究方向：圖論及其應用。

陜西省自然科學基礎研究計劃項目(2013JM1023)；陜西普通本科高等學校教學改革研究重點資助項目(13BZ56)；陜西省教育廳科研計劃基金項目(14JK1225)；商洛學院教育教學改革研究項目(14JYJX133)。

10.13990/j.issn1001-3679.2014.04.015

O157.5

A

1001-3679(2014)04-0493-03