Strong Edge-coloring And Star Edge-coloring Of Graphs

In this Ph.D.dissertation,we are interested in strong edge-coloring and star edge?coloring of graphsA proper k-edge-coloring of a graph G is a mapping φ:E(G)→ {1,2,...,k} such that φ(e1)≠φ(e2)for any two adjacent edges e1 and e2.If G has a proper k-edge-coloring,then G is proper k-edge-colorable.The chromatic index χ’(G)of G is the smallest integer k such that G is proper k-edge-colorable.A proper k-edge-coloring φ of G is called a strong k-edge-coloring if any two edges at distance at most two get distinct colors.If G has a strong k-edge-coloring,then G is strongly k-edge-colorable.The strong chromatic index,denoted by χ’s[(G),of G is the smallest integer k such that G is strongly k-edge-colorable.A proper k-edge-coloring φ of G is called a star k-edge-coloring if there does not exist bichromatic paths and cycles of length four.That is,at least three distinct colors are used on the edges of every path and cycle of length four.If G has a star k-edge-coloring,then G is star k-edge-colorable.The star chromatic index,denoted by X’st(G),of G is the smallest integer k such that G is star k-edge-colorableBy the definitions,it is straightforward to see that χ’s(G)≥ χ’st(G)≥(G)≥△.The strong edge-coloring of graphs was introduced by Fouquet and Jolivet(1983)In 1989,Erdos and Nesetril put forward the following famous conjecture:for a graph G,if △ is even,then χ’s(G)≤<5/4△2;if △ is odd,then χ’s(G)≤5/4△2.The conjecture was confirmed for the case △≤3,whereas it remains open for the case △≥ 4.In 1990,Faudree et al.first considered the strong chromatic index of planar graphs and proved that if G is a planar graph with △≥ 3,then χ’s(G)≤4△+4.They also constructed a class of planar graphs with △≥ 2 and χ’s(G)=4△-4.In 2013,Hocquard et al.proved that if G is an outerplanar graph with △≥3,then X’s(G)≤3△-3,and pointed out that this upper bound is tightLiu and Deng(2008)introduced the concept of star edge-coloring of graphs and showed that every simple graph G with △≤7 satisfies χ’st(G)≤[16(△-1)3/2].In 2016,Bezegova et al.investigated the star edge-coloring of outerplanar graphs by showing that every outerplanar graph G has χ’st(G)≤[L1.5△]+12,and conjectured that the constant 12 can be replaced by 1.In this Ph.D.dissertation,we study the strong edge-coloring of some graphs(includ-ing planar graphs with maximum degree 4,outerplanar graphs,and chordal graphs),and the star edge-coloring of some graphs such as planar graphs,K4-minor free graphs,out-erplanar graphs,and graphs with maximum degree 4.The dissertation consists of six chapters as follows.In Chapter 1,we collect some basic notation and give a detailed survey in the related fields.And we give the main results obtained in the dissertation.In Chapter 2,we study the strong edge-coloring of planar graphs with maximum degree 4 and prove that every planar graph G with △=4 is strongly 19-edge-colorable,which improves the currently known result that this kind of planar graphs are strongly 20-edge-colorable.In Chapter 3,we characterize the class of outerplanar graphs G having △≥ 3 andχ’s(G)=3△-3.That is,we show that if an outerplanar graph G does not contain several specific configurations as a subgraph then χ’s(G)≤3△-4.Chapter 4 is devoted to discuss the strong edge-coloring of chordal graphs.The main result is as follows:if G is a chordal graph,then χ’s(G)≤△2-2△+3.It shows that the strong edge-coloring conjecture holds for this class of graphs.In Chapter 5,we focus on the star edge-coloring of some graphs.In particular,we establish some better upper bounds for the star chromatic index of planar graphs.Precisely,we prove that if G is a planar graph,then the following conclusions hold:(1)χ’st(G)≤2.75△+18.(2)χ’st(G)≤2.25△+6 if G is K4-minor free.(3)χ’st(G)≤[1.5△]+18 if G has no 4-cycles.(4)χ’st(G)≤[1.5△]+13 ifg(G)≥5.(5)χ’st(G)≤[1.5△]+3 if(G)≥8.(6)χ’st(G)≤[1.5△]+5 if G is outerplanar.In Chapter 6,we obtain the following two main results on the star edge-coloring for general graphs with maximum degree 4:(1)If G is a graph with △=4,then χ’st(G)≤14.(2)If G is a bipartite graph with △=4,then χ’st(G)≤13.