极大外平面图的邻强边色数.pdf

第卷第期经济数学
年月
极大外平面图的邻强边色数‘
香进步
甘肃工业大学,兰州,
李敬文
兰州铁道学院计算机教研室,兰州,
摘要本文证明了对极大外平面图,△二名,△十,且石△十,当且仅当存在两个
最大度点相邻其中△、石分别表示图的最大度和邻强边色数
关键词图,极大外平面图,郁强边色数
引言
网络、通讯技术等提出了图的邻强边染色问题
定义月图,的一个一正常边染色,是映射
厦,,二,
使得相邻边,,任有,护
定义〔卜习对图‘,,一一正常边染色,若使得任意“任有笋,其中
任,则强为,的一一邻强边染色,简记为一,并称
认的一
为图的邻强边色数。
在」中有猜想对之的连通图,除圈外,有
太,二△
其中△表示的最大度
定义门若是一个平面图且在的一个面的边界上时,称为外平面图,且称
该面为外部面若为外平面图,“任‘,“告‘,而十“不为外平面图时,称为极
大外平面图
主要结果
引理闭若为一连通外平面图,则至少出现如下情况之一
存在两个度点相邻
存在一个度点与一个度点相邻
存在两个度点共邻于一个度点
国家自然科学基金资助项目
收稿日期一一
经济数学第卷
引理对之极大外平面图,是一连通的,且引理中的不出现此引
理显然成立
定理记。表个点的完全图,则
儿
儿一。
其中一。表示从‘中去掉一边·
定理是显然的
定理对】之的极大外平面图,
蕊△,若最大度点不相邻
石,△,若最大度点相邻
对的极大外平面图,显然△全若△,」已证明结论为真对
△之,仅证△二当△之时,与△完全一样证明结论为真,
使用数学归纳法证明· 当时为扇图。,易见结论为真·设一全时
结论为真,下推时结论为真,分两种情况
情况若最大度点不相邻根据引理,再分两种子情况
情况若度点与度点相邻此时由于是极大外平面图,所以“的另一邻点
一定与相邻,对此,设叮二‘· 对此,’二一,所以结论为真若△‘,由
仁」知此时结论为真若△叮,注意到此时当之时,极大外平面图,的度
时,全同时,在中有两个公共邻点“、,,且〔
情况若令的另一邻点为,此时必有“,任
设’的一为,其中种色分别记为,,,,,气此时,由之知
之
若,,则全分和两种情况,只对详证如下
若不妨设,,,,
若,,且
当,,,,时若,,,令,二,
,习二妙,习任￡,,显见是的一八若,
,,令二,,二习刁,砂〔,,
显见,是的一。由数学归纳法知乙二
若“,,但“护此时极易从’的得的一法详证略去
若“,,,,但笋。此时,易证结论成立
若“,此时极易从’的一法得的一法,详证略去
若,则三此时易从’的一法得的一法
情况。若,则二、兰
此时△’或当△叮二时,由归纳假设知公,’当△’时,由〕知
乙,‘二或或从归纳假设知二,叮二,对此,可按,或“,二
或,二且或且分别证明,由叮的一法得的
一法详证略去
第期鲁进步李敬文极大外平面图的邻强边色数