一类平面图的强边着色  

Strong Edge Coloring of a Class of Planar Graphs

作　　者：薄朝升[1] 谢德政[1] 

机构地区：[1]重庆大学数学与统计学院,重庆401331

出　　处：《重庆工商大学学报（自然科学版）》2011年第2期122-124,共3页Journal of Chongqing Technology and Business University:Natural Science Edition

摘　　要：图G的强边着色是正常边着色且任何长为3的路的边不着双色.图G的强边色数是G的所有强边着色中使用色数的最小者,记为χ's(G).证明了如果图G是平面图且满足g(G)≥14,则χ's(G)≤︱5Δ2-2Δ+1/4︱,其中g(G)表示图G的围长.A strong edge coloring of a graph G is a proper edge coloring such that no two edges with the same color lie on a path of length 3.The strong edge chromatic number of G is the smallest number of colors required to obtain a strong edge coloring of G,denoted by χ′s（G）.We prove that if graph G is planar and g（G）≥14,then χ′s（G）≤ [5Δ2-2Δ＋1/4] colors,g（G） indicate the girth of G.

关 键 词：强边着色 边着色 平面图 

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