若干图的广义字典积的全染色  

Total Coloring of the Generalized Lexicographic Product of Some Graphs

作　　者：田双亮[1] 孙向涛[1] 

机构地区：[1]西北民族大学数学与计算机科学学院,甘肃兰州730030

出　　处：《山西大学学报（自然科学版）》2013年第2期152-155,共4页Journal of Shanxi University(Natural Science Edition)

基　　金：国家民委科研项目(10XB01);中央高校基本科研业务专项资金(zyz2012077)

摘　　要：设G是具有顶点集{t0,t1,…,tn-1}的轮,或扇,或星,其中t0为最大度点,且n≥5.G[hn]是图G与顶点不相交图序列hn=(Hi)i∈{0,1,…,n-1}的广义字典积,其中每一个Hi为m阶简单图.论文得到了以下结果:(1)若H0为完全图的补图,则G[hn]的全色数为(n-1)m+1;(2)若H0为完全图,则G[hn]的全色数为mn;(3)若H0为二部图,则G[hn]的全色数为Δ(H0)+(n-1)m+1,其中Δ(H0)表示图H0的最大度;(4)若H0为m阶圈,m≥3,则G[hn]的全色数为(n-1)m+3.Suppose that G is a wheel,or fan,or star with vertex set {t0,t1 ,,t.-1 } ,where to is the vertex with maximum degree and n≥5. Let G[hn] be the generalized lexicographic product of graph G and a se- quence of vertex disjoint graphs hn= （Hi）,where each Hi is a simple graphs with m vertices. The following results are obtained：（1）If H0 is the complement of a complete graph, then the total chromat- ic number of graph G[h,] is （n--1）mq-1;（2）If H0 is a complete graph,then the total chromatic number of graph Gl-hn-] is mn; （3）If H0 is a bipartite graph,then the total chromatic number of graph G[h.] is A（H0） ＋（n--1）m＋l,where A（H0） denotes the maximum degree of H0;（4）If H0 is a cycle,then the total chro- matic number of graph G[h.] is （n--1）m＋3.

关 键 词：广义字典积 全染色 全色数 

分 类 号：O157.5[理学—数学]