On The Strong Edge Coloring Of Graphs

A strong edge coloring of G is an edge coloring such that two edges within distance two receive different colors.The strong chromatic index,denoted by χs’（G）,is the minimum number of colors such that G has strong edge coloring.The main challenge of strong edge coloring is Erdos conjecture:χs’（G）≤5△2/4 if △ is even and χs’（G）≤（5△2-2△+1）/4 if △ is odd.The（s,t）-relaxed strong edge coloring is the extention of strong edge coloring.For two nonnegative integers s and t,an（s,t）-relaxed strong k-edge-coloring is a mapping c:E（G）→[k],such that for any edge e,there are at most s edges adjacent to e and t edges which are distance two apart from e having the color c（e）.The（s,t）-relaxed strong chromatic index,denoted by χ（s,t）’（G）,is the minimum number k such that G has an（s,t）-relaxed strong k-edge-coloring.In this paper we prove the following results:1.If G is a graph with mad（G）<3 and △≤4,then χ（1,0）’（G）≤3△;2.In the cases of △=3and △=4,for different mad（G）,we prove an upper bound for χ（1,0）’（G）;3.If G is a planar graph with △≥4 and g≥7,then χ_1,0’（G）≤3△-1.