sm+∨+kn,n的边色数和均匀全色数.pdf

第卷第期
拓年月拓
。。,。的边色数和均匀全色数‘
张玉栋, 都自军, 何尚录, 强会英‘张忠辅,,
兰州交通大学数理与软件工程学院,甘肃兰州,
西北师范大学数学与信息科学学院,甘肃兰州,刀
摘要本文得到了十阶星和完全等二部图联图的边色数和均匀全色数
关键词完全等二部图,联图,边色数,均匀全色数
中图分类号文献标识码
主题分类号刃
引言
图的染色问题在实践问题中有着重要的应用川,但是对于一个图的色数算法一为
问题本文给出阶星和完全等二部图联图的边色数和均匀全色数
定义〕设,是简单连通图,是正整数,是从到,,⋯,的
一个映射,使得对任意的,、任,“并,有二尹、,则称为‘的一个正常的
一边染色简记成,而
义,一
称为的边色数
对于简单图,有侧△‘簇’簇△‘,其中△引表示的最大度若‘二
乙‘,则称‘为第类图若,‘乙‘,则称‘为第类图
定义」对于简单图,,是正整数,是从到,,⋯,的一个
映射,使得
任意的,,任君‘,尹二,有二尹、
任意的邵任,尹,有尹。,并娜,尹二,
则称为‘的一个全染色简记成而
‘一,
称为的全色数
年,提出如下猜想
猜想〕若‘是一个简单图,则
△延,蕊△
基金项目国家自然科学基金。
收稿日期洲】一一
第期张玉栋,郝自军,何尚录,强会英,张忠辅,,。的边色数和均匀全色数一一
其中△‘表示‘的最大度
已有一些特殊图,猜想为真,但是如何确定一个较为复杂的一类图的全色数,却是一个
十分困难的问题为此,在一些实际问题中提出了均匀全染色的概念
定义对于简单图‘,在满足定理和外,还满足
从、一科玛,,,,⋯,,
则称为‘的一个均匀全染色简记成,而知一‘称为
‘的均匀全色数
定义〔,〕设图‘与万是点和边都不相交的简单图,若‘万‘万,五‘
邵任,任,则称是与的联图
猜想对于简单图‘,有‘‘蕊乙‘十
猜想阁对于完全图‘,有石二沁‘
在这篇文章里我们给出了。,。的边色数和均匀全色数,文中没有加以说明的术语和
记号可参见〔,
。。的边色数
引理是一个简单图,凡任且。△,如果‘凡是一个森
林,则△其中,引凡是凡关于‘的导出子图
引理对于完全图,有
一三,
义‘凡
, 二
定理‘,。,, ‘,,。,
证明因为联图,,是一个完全图由引理,易得’,,二
显然,姚,且‘「凡」是一个森林由引理,结论成立
定理‘、,, ‘凡,。,
证明显然,△,,,,由嗯定理,得‘,,或‘,,
考虑到五个点的图中不含有三条边的匹配,‘,,是不可能的因此结论成立
当妻时,凡,证明方法同定理,在此不再详述
定理当多时,有’。凡,。二
证明我们考虑以下两种情形
情形当〕时,由引理易证结论成立
情形当二时,令是从。,。。,。到集合,,⋯,的
映射
。。。,,,⋯,
。,。、,,,⋯,,,,⋯,一
经济数学第卷
。一,。
所以是。,的一法因此,结论成立
综上所述,有以下结论成立
定理对任意的正整数,,用乙表示最大度,有
△

、少
屯二,
产一
义‘凡,尺△
其他
。,。的均匀全色数
引理‘是一个简单图,有石〕△十
引理对