文档介绍：第卷第期
拓年月万
。的均匀全染色’
马刚‘张忠铺,
西北民族大学计算机科学与信息工程学院,甘肃兰州田
兰州交通大学应用数学研究所,甘肃兰州
摘要对一个正常的全染色满足各种颜色所染元素数点或边相关不超过时,称为均匀全染色,其所用
最少染色数称为均匀全色数就星凡,。与路的联图凡,凡,得到了在,不同取值情况下的均匀全色
数
关键词星,路,联图,均匀全色数
中图分类号巧文献标识码
引言
具有重要的实际意义和理论意义的图的染色问题,是图论研究的主要内容之一,图的染色
的基本间题就是确定其各种染色法的色数已经公认,确定图的有关色数是一个十分困难的问
题图的全染色〔‘一〕猜想已有年,年以来张忠铺、王维凡等人先后又提出图的均匀全染
色〔一〕的概念和相关猜想,但是所知结果甚少本文给出了星,。与路的联图的均匀全色
数
相关定义及引理
定义〔‘一对图,的映射,川卫一争,,⋯,到,若满足下列条件
,。任,,任百,且尹。,有尹。
,二任百,并叨,有珊尹
,任,二任￡,且尹,有并邵,笋哪
’,引,,⋯,剧,有一‘一乓一二
则称为‘的一个一均匀全染色法,简记作一而
‘一
称为的均匀全色数其中,‘从‘,任,二
显然有‘‘七△‘,其中△表示‘的最大度数
猜想困对简单图‘,有
带基金项目国家自然科学基金资助项目
收稿日期一田一’
一一经济数学第卷
‘‘乙,且‘
其中为‘的全色数
定义仁,〕设图‘与万有门万必君‘门百万必若‘万满足

君百二任,。任
则称为‘与的联图
引理护了对阶完全图,有
,二
义‘凡
,三
引理‘〕若万是‘的子图,则有,三,
引理圈闭对简单图‘,若斑凡〕无圈,则有△
其中凡二。△,。任,凡训。△,琳任,
为‘的均匀边色数
文中未加述及的术语、记号可参见「一」
主要结论及其证明
记
在以下的讨论中, 阶星,。为,。,,,⋯,君天卜。
记
。‘,,⋯, 阶路。。,⋯。。
引理对,,。。,有△,。。刀十。
定理当时,对,。尸有
,,。
证明以下分两种情形对本定理予以证明
当时,则,,,尸,凡,从而由引理知‘凡,,尸‘凡二,所以
此时结论成立
当之,由定义和引理知义‘,。尸全,为了证明结论成立,仅需
给出,。尸,的一个十一法
令为
。‘,,,⋯,
。。, , ,,⋯,

。。

、,,·二,
对此,显然有
, , ,
蒯,
由此可见,是,。一℃法,所以此时结论成立
综上所述,定理为真
第期马刚张忠铺凡。的均匀全染色一一
定理当时,对,。尸有
‘、,。,,
,
证明以下分四种情形对本定理予以证明
当。时,则凡,,尸二,从而由引理知‘凡,,尸。凡,所以
此时结论成立
当时,易见△,,从而有。,七又因,是
凡的一个子图,则由引理和引理知‘,尸‘‘凡所以‘,,尸,
从而此时结论成立
当时,易见△,,,,从而有‘,。凡为了证明结论成
立,仅需给出,,。尸的一个一法
令为
。。,。。二。
二。。。二
。。。,。,。
由此可见,显然是,的一法,所以此时结论成立
当七