pn∨pm的邻点可区别边染色.pdf

第卷第期经济数学
年月
尸、尸的邻点可区别边染色
马明‘’“,刘华‘,“,陈进源‘,赵鹏‘,张忠辅“
兰州大学数学系,甘肃兰州,
西北民族大学数学系,甘肃兰州,
摘要对于图的郁点可区别染色,给出了路的联图尸。尸阴的部点可构别边色数
关键词图,路,联图,都点可区别色数
引言
由计算机科学等引出的点可区别染色问题仁,一“习,是一个十分困难的问题,十多年来在刊物
上仅有九篇论文「〕减弱了要求,提出了邻点可区别的边染色问题本文给出了。‘。邻点
可区别的边色数

定义‘一‘」对图,,映射,,⋯,,记丫任如
果
对,任,并,有半
对〔,有祥
则称为的邻点可区别边染色简记为一,称
太一
为的邻点可区别色数显然有
、全乙
其中△表示的最大度数
定义设对图与,有必曰,若图与满足

任,任
则称为与联图
主要结果
本文讨论了阶路与阶路的联图尸,尸二的邻点可区别边染色,得如下结果不失一般
国家自然科学基金资助项目
收稿日期一一
一一经济数学第卷
性,设全
定理设尸。尸。为阶路与阶路的联图,则

全


,
一、
太,,

之



、或之,
定理证明
引理闭对的连通图,若有最大度点相邻,则有
名全△
其中乙表示的最大度数
以下给出定理的证明,记,⋯嘛尸,⋯,
定理的证明情形当饥,之时,此时△,只要给出尸。尸的一个一法
即可,令为
‘, ,,
、, , ,,⋯,一
,一,
对此,有
,,⋯,
二,
,,
。一一,一,
,一一,,
, ,
所以,是,尸的一法,从而此时定理为真
情形当,,时,此时最大度点相邻且乙,,由引理,只需分别给出
尸尸,,尸尸,的一法和一法即可,见图,图
己
一
。
图尸﹀仲法
尸尸的一法
当
情形,时,由引理见图给出尸尸的一法
第期马明刘华陈进源赵鹏张忠铺的邻点可区别边染色一一


图,的一法
情形当二,时,最大度点,,相邻且乙,由引理,只需给出尸,尸的
一法即可,令为
, ,,⋯,
‘, ,,⋯,

,、,,⋯,一
对此,有
,,⋯,,
,,⋯,,, ,
,,
,,,
。一一,, ,十
, , ,
所以,是尸,尸的一法,从而此时定理为真
情形当二,时,所有点,,。,,,均相邻,由引理
乙,乙,全
但尸尸不存在一法,下面用穷举法证明,即用,,,给出所有尸尸的正常染
色法,考察是否存在一法不失一般性先用,,染关联的三条边,作如下映射
, ,
再对着色,此时只能有或,
当,时的情形

,,不是

, 之
一、
,,不是


则只能有姚,,不是
当时,只能有,此时只能有,这样导致
,,,,,,不是法
综上所述,尸的所有种正常边染色均不是法所以,尸尸不存在
一法下面给出。尸的一法
,

对此,有
,,
一一经济数学第卷
,,
,,
弋,,
所以,太、尸尸
情形当,全时,乙十,由引理