文档介绍：第卷第期经济数学
年月八蹂。,熬
尸。的邻点可区别全染色‘
晃福刚强会英闻丽宏王文杰王治文张忠铺
兰州交通大学应用数学研究所甘肃兰州,。。了。
摘要把星。,,· ,“二中的每一个点与路知,刁,。,· ,队中的每一个点相连,得到路和星的联图。记
为尸,本文给出了尸、二的那点可区别全色数
关健词路,星,联图,邻点可区别全染色
前言
定义对简单图,,若存在映射和自然数,‘一书,,⋯,满足
①二任,有。护,共,共
②,任井,有。共二
③半
则称了为的一个一邻点可区别全染色法,简记作一,而效彩
一称为的邻点可区别全色数其中,一一任,任

定义〔口设和是色边不交的完全图,,
王任,。〔则称为和的联图
猜想对简单图,吞互以十其中乙表示的最大度
本文得到了阶路州和。阶星及,的邻点可区别全色数文中未加说明的术语和记号,
可在「一中找到
主要结果
凡三,
引理,二当之时,石
三
引理,」若动二的乙,且任,则几全乙〔
引理乙
以下设尸,劝二⋯二。,,。,,⋯, 卜,,二,
定。“观如一有、一十乙髻川兰全
基金项目,国家自然科学资助项目
收稿口期一一
一一经济数学第卷
证明①当二二时,或从,时,,,或,由引理知结论为
真,即石,义。尺
②当,时,即尸,尸,由于最大度点相邻,故概根据引理,抓尸二
全乙十若要证明结论成立,仅需给出它的一个一丁法令
。二,,,二,,,,,,
二一,公。一,二,,,二二,。
其中,,,,,,二,,,,,,,,,它们互不相同,故可
知它是一
③当之时,由于最大度点相邻,故根据引理知荔彩州之为证结论成立,
仅需给出〔。一法
一,,,,⋯,次,,,⋯,别一
十,了,二十,。二一,,,⋯二上二一定缺,
一色一,,⋯,。一,故共认川缺色,缺色,故半,
综上所述,定理结论为真
刀,
从, ,
···用··,·之··,一互,刀
证明①当,二。时,尸,尸尸,由定理中的②可知结论成立
②当、,时,州。,令为
, ,。二, 二,,,
, ,二二一, ,
二, , ,二,二, ,
任,护,易见了是几的一定理结论为真
③当。之,时,令为
】,, 二,,⋯,,二一二,,⋯
阴,,。,一,,,二一,一,,⋯,。,

易知,任,们并的,故是它的。十一定理结论为真
二刀,
定理对。之刀,有乙。尸州。
阴,月
证明①当。二时,令为
二,二,。。干,,,
尸一二,,。。,刃,,,
,,。。,二,
, ,
易知,〔,共,,故是的一法
②当舰,时,令为
二,,⋯,阴,。。叨,,。。“一,
,,⋯,一,丈,,一,,⋯,,
第期晃福刚强会英闰丽宏王文杰工治文张忠铺。的邻点可区别全染色一一
。二,二,,⋯,。一,叨,。
当二时,
工二。一叨,。一加一二,二, ,
、
二。了,二,了二一了。‘户,一丈、,乙’“’“’一百夕刁又竺招卫少一阴十任·
当阴三。时,
三,
一,一了一,一了一,一,了,一,,一‘,,,一三
易知,。任,笋,故是州的。卜法
综上所述知,定理结论为真
定理