关于最大度是4的平面图的18-强边染色  

STRONG 18-EDGE COLORING OF PLANAR GRAPHS WITH MAXIMUM DEGREE 4

作　　者：李明 张霞 Li Ming;Zhang Xia(School of Mathematics and Statistics,Shandong Normal University,250358,Jinan,China)

机构地区：[1]山东师范大学数学与统计学院,济南250358

出　　处：《山东师范大学学报（自然科学版）》2018年第4期401-405,共5页Journal of Shandong Normal University(Natural Science)

基　　金：山东省自然科学基金资助项目(ZR2014JL001)

摘　　要：图G的强边染色是一种边染色使得任何长至多为3的路上的边都染不同的颜色.使得图有一个强边染色的最小颜色数称为图的强边色数.当图G是平面图且最大度为4时,Wang等人证得其强边色数不超过19.在本文中,我们证明:对最大度为4的平面图,若它是一个非18-强可染的边数极小图,则它一定不存在至多含三条边的非平凡边割.A strong edge-coloring of a graph G is a proper edge-coloring such that edges of every path of length at most3are colored with different colors.The smallest number of colors when G has a strong edge coloring is called the strong chromatic index of G.When G is a planar graph and the maximum degree is4,recently it was proved that the strong chromatic index of G is at most19by Wang et al.In this paper,we prove that if a planar graph with maximum degree4is a minimal graph with non18-strong-edge coloring,then it must contain no nontrivial r-edge-cuts for r=1,2,3.

关 键 词：强边染色 平面图 边割 拼接染色 

分 类 号：O241.82[理学—计算数学]