山东大学学报（理学版）
山東大學學報（理學版）
산동대학학보（이학판）
JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
2015年
8期
10-13
,共4页
平面图%强边染色%强边色数%圈
平麵圖%彊邊染色%彊邊色數%圈
평면도%강변염색%강변색수%권
planar%strong edge coloring%srtong chromaic index%cycle
图 G 的强边染色是指对图 G 的边进行染色，使得距离不超过2的任意两条边染不同的颜色。任何一个平面图都可用4Δ＋4种颜色进行强边染色。证明了当平面图没有 k-圈（4≤k≤10）且3-圈不相交时（即每个顶点至多关联一个3-圈），必定存在一个3Δ＋1种颜色的强边染色。
圖 G 的彊邊染色是指對圖 G 的邊進行染色，使得距離不超過2的任意兩條邊染不同的顏色。任何一箇平麵圖都可用4Δ＋4種顏色進行彊邊染色。證明瞭噹平麵圖沒有 k-圈（4≤k≤10）且3-圈不相交時（即每箇頂點至多關聯一箇3-圈），必定存在一箇3Δ＋1種顏色的彊邊染色。
도 G 적강변염색시지대도 G 적변진행염색，사득거리불초과2적임의량조변염불동적안색。임하일개평면도도가용4Δ＋4충안색진행강변염색。증명료당평면도몰유 k-권（4≤k≤10）차3-권불상교시（즉매개정점지다관련일개3-권），필정존재일개3Δ＋1충안색적강변염색。
A strong edge coloring of a graph G is an assignment of colors to the edges of the graph such that any two edges at distance at most 2 receive distinct colors.It is known that every planar graph has a strong edge-coloring with at most 4Δ+4 colors.It is proved that planar graph G has a strong edge-coloring with at most 3Δ+1 colors if G has no k-cycles with 4≤k≤10 and no intersecting 3-cycles (that is,every vertex is incident with at most one cycle of length 3).
