文档介绍：第卷第期经济数学
年月
△的外平面图的邻强边染色‘
刘林忠,焦永兰张忠辅
兰州铁道学院管理工程系, 兰州铁道学院应用数学研究所,
王建方
中国科学院应用数学研究所,北京,
摘要对图,,一正常一边染色称为,的一部强边染色,当且仅当对任意有
〔〕并〔」,其中〕任,、表示染边的色并称蕊伍存在的一龙
种色的郁强边染色为的邻强边色数本文证明了对。的一连通外平面图,有石
关键词外平面图,正常边染色,邻强边染色
引言
图的强边染色产生于计算机科学,有很强的实用性自从川中提出图的强染色概念后,由
于此类问题较之一般的染色要难的多,因此图的强染色理论未得到很好的发展,直到最近有关
学者才对此类问题进行了初步的研究“〕
定义比〕对图,一正常一边染色称为,的一强边染色简称一,
当且仅当对任意,任有〕并〕,其中〔〕二〔,表示染
边的色并称名王川存在的一一为,的强色数
定义对图,一正常一边染色称为,的一邻强边染色简称一,
当且仅当对任意任有「司并「,其中司王任,表示染
边的色并称“川存在的一一为,的邻强边色数
定义设,为一平面图若,的所有顶点都在一个面的边界上,则称
,为一外平面图,并称边界上的点和边为,的外点和外边其他边为内边
关于图的邻强边染色,刘林忠和张忠辅等提出了如下猜想
猜想对的连通图,,笋圈,则
乙镇乙,镇△
我们已证明了圈,扇,轮,树,完全图,完全多部图,一图和外平面图等该猜想成立本
文仅研究了乙的外平面图的邻强边染色
文中未定义的其它符合和术语参考文献「
主要定理
引理川设为乙的一连通外平面图,则至少出现如下情况之一
国家自然科学资金资助课题
收稿日期一一修改稿一一
第期刘林忠焦永兰张忠辅王建方△二的外平面图的邻强边染色一
有两个度点想相邻
有一个度点“和一个度点相邻记卜。
引理设‘为乙“的一连通外平面图若不出现引理中的,则至少存在一组
引理中的中的,,二,使得〔
证明用反证法若引理中的不出现,但任一组引理的的“,,都有在
对所有这样的“,,,去掉及其相关联的边,添加边“,得一新图‘‘显然为
。的一连通外平面图,但,中不出现引理中的和,矛盾引理得证
引理设为乃的一连通外平面图,且度点的个数至少为。若不出现引理
中的,由引理知至少存在一组满足引理中结论的,,,使得任记“
万,,二万,若,,,,,一般的若任,
则记。,一,,,弋“,外一,,,,⋯⋯显然在有限步后必存在
整数,使得孙户任,户为十,去则必存在一组上述,,。,且户,与为十,中至少
有一个度点
证明用反证法设为满足引理中条件的一连通外平面图假设任意满意引理中条件
的“,,都有户十,二为、二构造如下图’去掉所有满足引理中条件的,,,,
夕及,夕汤,,,⋯,,添加新边户夕户对其他度点‘及邻点‘,‘因为不出现引
理中的,所以‘二,,去掉“‘,同时添加新边创‘显然这样得到的口仍乙
的一连通外平面图,但’中不再有一度点,矛盾综合以上可知结论成立
定理设为乙二的仅有个度点的一连通外平面图,则太二
证明情况若二设卜,其中三
以一个一度点为起点,按顺或逆时针方向的顶点依次为“,“,⋯,“,则另一个一度
点必为普,·边,