文档介绍：第卷第期经济数学
年月
代三的邻点可区别的强全染色
马生全‘李敬文马明‘张忠辅“
西北民族数学系,兰州,
兰州交通大学计算机系,兰州,
兰州交通大学应用数学研究所,兰州,
摘要对简单图,,乏,乏,,称介为的次方图,其中
,表示,在中的距离设为用色时的正常全染色法,对,满足护,其中
任任,则称为的邻点可区别的强全染色法,简记
作一,且称。一为的郁点可区别的强全色数本文得到了“
时的加鑫,其中。为阶路
关键词路的次主图,全染色,郁点可区别的强全色数
引言
, 、‘, 、, 、、‘一。,,、,
足义月盯图仁出,映射泌一悦沼,⋯,少满足仕息相邹田边,有井
‘,则称是的一个一正常边染色,简记作一
定义〕若对图,的一个一的,又满足对任意的任,且笋
,则称为的一个临强边染色,简称作一,且称
乙二二一
为的临强色数,其中咬任
定义图设,是阶数不小于的简单连通图,是自然数,了表示映射
日。三一,,⋯,
且满足
,任,并,共
任,并,笋,笋
任,并,其中
任
则称为的临点可区别的全染色法,简记作一,且称
,一
为的临点可区别的全色数
定义闭设,是阶数不小于的简单连通图,是自然数,表示映射
日卜二,,⋯,。
收稿日期一一
一一经挤数学第卷
且满足
,任,并,并
任,笋,并,并
〔,并,其中
王任任
则称为的临点可区别的强全染色法,简记作一,且称
毛,二】一
为的临点可区别的强全色数。
在「中得到了路、圈、星、扇、轮、完全图、完全二部图和树的邻点可区别的强全色数后,提
出了如下猜想
猜想’若为阶数不小于的简单连通图,则
毛二镇十〔
其中【司表示不小于的最小整数,等号成立当且仅当为完全图。,其中’一
文中符号、术语可参考〔、、
主要结果
引理若中最大度点相邻,则,乙
此引理显然,证明省略
定理对,有
,
,尸,’一
证记路尸。二,。当时,尸参在【」中已有结论当时汕尸乏且
度点相邻,现给出川的一法
‘, ,
,二,二
对有
,,, ,,,,
,,,,‘,,,,
所以是川的一法,从而此时结论为真
当时,此时,所以二尸,通过穷举代不存在一法,现给出
其一法
二,,
一, ,
,二
对此有
,,,, ,,,,,
今,,,,, ,,,,,“,,,
第期马生全李敬文马明张忠辅只二的邻点可区别的强全染色一一
所以,是代的一法,从而此时结论为真·
当时,此时有度点相邻,所以,尸三》令为对叭二,。点边循环用色、
、、、、染对,,⋯循环用色、、染对‘,‘,。⋯循环用色、、染
,‘,,⋯,,循环的为、、、、、、、、、、、、、、对此有
。一,,,,,。,,,当三且二时,,一,
,,,,。,,,,当二且二时,,一,,,,,,
,,,,当二且三时,。一,,,,,。,,
,当三且三时,。一,,,,,,。,,,,所以
是烈的一法,从而此