Strong Edge Coloring Of Planar Graphs

All graphs considered in this thesis are finite,simple and undirected.Let G be a graph,we use V(G),E(G),F(G),?(G)and g(G)to denote its vertex set,edge set,face set,the maximum degree and the girth.A strong k-edge coloring of G is a coloring of the edges of G,?:E(G)?{1,2,...,k},such that if the distance between e1 and e2 is at most 2,then ?(e1)??(e2).?s(G)=min{k| G has a strong k-edge coloring}.Erdos and Nesetril put forward a famous conjecture about the upper bound of ?s(G)in 1989.Let G be a graph whose maximum degree is ?,then(1)?'s(G)?4/5?2,if ? is even;(2)?'s(G)?1/4(5?2-2?+1),if ? is odd.Driven by this conjecture,scholars have done lots of research work on strong edge coloring of graph,and got countless significant conclusions.In this master thesis,we mainly apply weighting methods,study the structural properties of related graph classes,focus on the upper bound of ?'s(G)of planar graphs without some short cycles and the upper bound of ?'s(G)of the graphs whose girth at least 5.This thesis includes three sections.In the first section,we show some related concepts and research status of strong edge coloring.In the second section,we prove the upper bound of ?'s(G)is 3?(G)+1 for planar graphs with no k-cycle(5<k<10)and the 3-cycle and 4-cycle are non-intersect each other.In the third section,for the planar graphs with g(G)>5,?(G)>6 and 5?circle do not intersect,we prove the upper bound of ?'s(G)is 4?(G)-1.