轮形图的全着色

杨鹏辉

(安徽财经大学统计与应用数学学院，安徽蚌埠 233030)

轮形图的全着色

杨鹏辉

(安徽财经大学统计与应用数学学院，安徽蚌埠 233030)

轮形图;全着色;弱全色数;强全色数

图的着色理论起源于1852 年 Francis Guthris提出的“四色猜想”［1］，自1965 年 Vzing［2］和 Behzad M［3］分别提出图的全着色概念后，全着色理论就在图着色理论中占有很重要的地位.1966年Behzad M首次提出超图，逐渐地着色理论被引入到超图中来.随着超图理论的不断完善，超图的全着色也逐渐被学者们所重视，现在超图的全着色更是学者们所热衷的研究对象.对于一般图中轮形图和扇形图的全着色，文献［4－5］中已经有了很好的结论.

1 基本概念

定义1［6］超图H的弱全着色(Weak Total Coloring)是映射

定义4顶点v的轮W(v)定义为S(v)□Cn，形如K1×Cn－1，其中S(v)是以点v为中心的超星(见图1)，Cn是超图中长度为n的线性超圈，星与圈的交点恰是圈中边与边的交点，中心v称为轮心，超星的边称为轮辐，圈的边称为轮边，如图2所示.

图1 超星

图2 轮形图

通过轮的定义可知，d(v)=Δ=E(S(v))=n，则轮共有2Δ=2n条超边，其中Δ条轮辐，Δ条轮边，还有Δ个3度点.文中用Δ表示超图中的最大度，其他的相关概念在文献［5－6］中均可以找到.

2结论

引理 1［9］设S(v) 是星，其边集合E(S(v))={E1，E2，…，EΔ} 则

2)证明轮的强全色数是M+1.

M+1种颜色用集合C={1，…，M+1}表示，定义映射φ∶V(H)∪E(H)→C如下

若减少一种颜色，使用M种颜色着色，当M=Δ时，根据强全着色定义可知，中心点v与Δ条超边就需要Δ+1种不同的颜色，则M=Δ种颜色不满足;当存在p{1，2，…，Δ}s.t.M=rp时，按照强全着色定义，超边Ep需要rp+1种不同的颜色，M=rp种颜色不满足.因此，(S(v))＞M.

［1］ORE O.The Four-Color Problem［M］.New York:Academic Press，1976.

［2］VIZING V G.Some unsolved problems in graph theory［J］.Uspekhi Mat.Nauk，1968，23(6):117 –134.

［3］BEHZAD M.Graphs and their chromatic［D］.Michigan State University，1965.

［4］黄斌，张先迪.一些图的全着色计数［J］.四川师范大学学报:自然科学版，1998，21(5):523－526.

［5］张忠辅，陈祥恩，李敬文，等.关于图的邻点可区别全染色［J］.中国科学A辑，2004，34(5):574－583.

［6］WANG Wei-fan，ZHANG Ke-min.Coloring of Hypergraphs［J］.Advances in Mathematics，2000，29(2):115 －136.

［7］HARARY F.Graph Theory［M］.London:Addison-Wesley Publishing Company，1969.

［8］贝尔热 C.超图-有限集合的组合学［M］.卜月华，张克民，译.南京:东南大学出版社，2002.

［9］杨鹏辉.星的全着色和计数［J］.重庆大学学报:自然科学版，2007，30(5):119－122.

Total Coloring of Wheels

YANG Peng-hui

(Department of Statistic and Applied Mathematics，Anhui University of Finance and Economics，Bengbu 233030，China)

The total chromatic number χT(H)of hypergraphHis the minimum number of colors needed to color the vertices and edges ofHso that the incident or adjacent elements have distinct colors.The total coloring of hypergraph contains weak total coloring and strong total coloring.In the paper，the characteristics of the total colorings of wheelW(v)were discussed ，and the chromatic numbers of them，(W(v))=Δ+1，(W(v))=M+1 were obtained.

wheels;total coloring;weak total chromatic number;strong total chromatic number

O 157.5 < class="emphasis_bold">文献标志码:A

A

1004－1729(2011)01－0008－03

2011－01－21

杨鹏辉(1981－)，女，安徽淮南人，安徽财经大学统计与应用数学学院讲师，硕士.