极大外平面图的星边染色

摘要：

如果图G的一个正常边染色使得G中没有长为4的路或4-圈是2-边染色的,则称此染色是G的一个星边染色.对G进行星边染色所需的最少颜色数称为G的星边色数,记作x′s(G).该文证明了最大度为4的极大外平面图的星边色数等于6,对任一n(≥8)阶极大外平面图Gn,有6≤x′s(Gn)≤n-1成立,并且上界和下界都是可达的.

关键词：星边染色、星边色数、极大外平面图

所属期刊栏目：26

分类号：O157.5(代数、数论、组合理论)

资助基金：国家民委科研项目10XB01;中央高校基本科研业务费专项资金zyz2011081

在线出版日期：2012-03-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：489-494