极大外平面图的星边染色  

Star edge coloring of maximal outer plane graphs

作　　者：邓凯[1] 田双亮[1] 

机构地区：[1]西北民族大学数学与计算机科学学院,甘肃兰州730124

出　　处：《高校应用数学学报（A辑）》2011年第4期489-494,共6页Applied Mathematics A Journal of Chinese Universities(Ser.A)

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

摘　　要：如果图G的一个正常边染色使得G中没有长为4的路或4-圈是2-边染色的,则称此染色是G的一个星边染色.对G进行星边染色所需的最少颜色数称为G的星边色数,记作X′_s(G).该文证明了最大度为4的极大外平面图的星边色数等于6,对任一n(≥8)阶极大外平面图G_n,有6≤X′_s(G_n)≤n-1成立,并且上界和下界都是可达的.A proper edge coloring of graph G is called star edge coloring if there is no path of length 4 or 4-cycle in G which is bicolored.The minimum number of colors required for a star edge coloring is called the star chromatic index of G and denoted by x_s′（G）.In this paper,it is proved that the star chromatic indices of maximal outer plane graphs with maximum degree 4 are 6,and 6≤x′s（G_n）≤n-1 for every maximal outer plane graph Gn with order n at least 8,and the lower and upper bounds are both attainable.

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

分 类 号：O157.5[理学—数学]