On The Strong Edge Coloring Of Graphs

In 1736,Swiss mathematician Euler discussed the problem of the Seven Bridges of Konigsberg in his paper,which brings a whole new branch of mathematics-graph theory.Since the four color conjecture has been put forward,the coloring problem of graphs become a very important research topic of graph theory.Graph coloring theory has a very important application in the fields of computer theory,of com-binatorial optimization,of information science and of network design.There are many branches of graph coloring theory,such as edge coloring,vertex coloring,sur-face coloring and total coloring etc.Among them,the most research,the results are more perfect is the graph edge coloring.The purpose of this paper is to discuss a special edge coloring-strong edge coloring of graphs.This paper consists of five chapters,the main contents are as follows:In the first chapter,we first give the basic concept and mark used in this paper,and introduces the background and research status of strong edge coloring of graph.Finally,we gives the main results.In the second chapter,we focus on strong edge coloring of sparse graphs.Hoc-quard et al.were first studied the strong edge coloring of subcubic sparse graphs.Recently,Bensmail et al.studied the strong edge coloring of sparse graphs with max-imum degree 4,they showed that every sparse graphs with maximum degree 4 and maximum average degree strictly less than 16/5(resp.10/3,17/5,18/5,19/5)can be strongly edge-coloured with 16(resp.17,18,19,20)colours.We improved the above results and proved that every sparse graphs with maximum degree 4 and maximum average degree strictly less than 61/18(resp.7/2,18/5,15/4,51/13)can be strongly edge-coloured with 16(resp.17,18,19,20)colours.In the second part of this chapter,we showed that every sparse graphs with maximum degree 4 and maximum average degree strictly less than 8/3(resp.14/5 can be strongly edge-coloured with 10(resp.11)colours.In the third chapter,we prove that if G is a graph with ?(G)? 6 and maximum average degree less than 14/5,then ?'s(G)? 3?(G)-1,and this implies that ?'s(G)?3?(G)-1 for every planar graph G with maximum degree ?(G)? 6 and girth g ? 7.Which improve the result of Wang:every planar graph G with maximum degree ?(G)? 6 and girth g?7,then ?'s(G)? 3?(G).In the fourth chapter,we first focus on the strong edge coloring problem of pseu-do Halin graphs.Pseudo Halin graphs are general generalization of Halin graphs.Shiu et al.first studied the strong edge coloring of Halin graphs and proved that the strong chromatic index of cubic Halin is at most 9.Recently,Hu et al.gave a upper bound about strong chromatic index of a general Halin graph:let G be a Halin graph with,maximum degree ? ? 4,then ?'s(G)?2?(G)+ 1.In this chapter,we show that ?'s(G)? 3?(G)-2 for any pseudo-Halin graph G with maximum degree??4.It is necessary to note that the upper bound 3?(G)-2 is close to the best possible bounds,because we find a pseudo Halin graph whose strong edge chromatic number is exactly equal to 3A(G)-3.At the end of this chapter,we will mainly discuss the strong chromatic index of K2,3-minor free graphs.We'll prove:if G is K2,3-minor free graphs,then ?'s(G)?4?-6 and the bound is sharp.In the fifth chapter,the end of this paper,we puts forward some research questions that can be further considered.