Research On The Strong Edge-Coloring Number Of Planar Graphs

The strong chromatic index of a graph G.denote ?s'(G)?is the minimum integer k such that the edge set can be k-colored requiring that each color class is an induced matching of G.We only consider simple graphs in this thesis.Let ? = ?(G)denote the maximum degree of graph G.In this thesis,we focus on the strong chromatic index of planar graphs.The goal of our research is verifying the following conjecture.s:For any planar graph G,we have ?s'(G)??2.In order to study this conjectures,we use a method,i.e.,proofs of contradiction,obtaining some structural properties for minimal counterexamples,and get some classes of graphs satisfying this conjecture.In the process of structural analysis,the system of distinct representatives(SDR)is a crucial tool.The research contents of this thesis can be divided into two parts.In the first part,we mainly discuss different properties of planar minimal counterexamples G which contradict the conecture.Planar minimal counterexamples G axe defined so that ?s'(G)??2+1 and|V(G)| + |E(G)| is as small as possible.In the second part,we study the strong chromatic index of planar bipartite graphs and planar graphs with maximum degree greater than or equal to 8.The main results of this paper are as follows:(1)If G is a planar bipartite graph,we have the strong chromatic index ?s'(G)? ?2,for?? 7.(2)If G is a planar graph with maximum degree ? ? 8,we have the strong chromatic index Xs'(G)? ?2.(3)Every planar minimal counterexample G has no vertices with degree of 1.(4)In any planar minimal counterexample G,we have d(x)+ d(y)?? + 2.for each edge xy ? E(G).(5)Any planar minimal counterexample G has no triangle which contains a 2-vertex,3-vertex or 4-vertex.(6)Any planar minimal counterexample G has no C4 which contains a 2-vertex.(7)Every planar minimal counterexample G is 2-connected.