两类平面图的关联色数  

Incidence Coloring Numbers of Two Classes of Planar Graphs

作　　者：张丽[1] 陈东灵[2] 

机构地区：[1]同济大学数学系 [2]山东科技大学信息科学与工程学院,山东青岛266510

出　　处：《同济大学学报（自然科学版）》2008年第3期392-396,共5页Journal of Tongji University:Natural Science

摘　　要：轮Wr+1(r≥3)是一个r阶圈加上一个新的顶点,再把圈上每个顶点与新顶点连上边所得到的图.新顶点与圈上顶点之间的边称为辐边,圈上的边称为边缘边.所谓花图Fr,m,n(r≥3,m≥1,n≥2m+1),是在轮Wr+1中的在每条辐边上分别嵌入m-1个新点,在每条边缘边上分别嵌入n-2m-1个新点所得到的图.所谓棱柱Qn(n≥3),是指Qn=(V,E),V={u1,u2,…,un}∪{v1,v2,…,vn},E={uiui+1,vivi+1,uivi,uivi+1|i=1,2,…,n},其中un+1=u1,vn+1=v1.通过给出花图Fr,m,n(r≥3,m≥1,n≥2m+1)和棱柱Qn(n≥3)的一种关联着色方法,确定了它们的关联色数.A wheel Wr＋1（r≥3） is a graph obtained from a cycle of order r by adding a new vertex and joining the new vertex to all the vertices on the cycle. The new edges between the new vertex and the vertices on the cycle are called spoke edges, the edges on the cycle are called rim edges. A flower graph Fr （r≥3, m≥1, n≥2m ＋ 1） is a graph obtained from Wr＋1 by inserting m - 1 new vertices in every spoke edge and n - 2 m - 1 new vertices in every rim edge. The planar graph Qn （ n≥3） called a prism is defined by Q. = G（ V, E）, V = { u1,u2, …, un } ∪ { v1, v2, …, vn } and E = {uiui＋l, vivi＋1, uivi, uivi＋1｜i=l,2,…,n}, where un＋1=u1,vn＋l=v1. Based onincidence coloring methods of Fr,m,n（ r≥3, m≥1, n≥2 m ＋ 1） and Qn（ n≥3）, the incidence coloring numbers of them are determined.

关 键 词：关联色数 关联着色 花图 棱柱 

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