The Relaxed Strong Edge Coloring Of The Graph

Let G be a finite and simple graph.For a graph G,we use V(G),E(G)and F(G)to denote its vertex set,edge set and face set,respectively.We usually denote by V,E and F instead of V(G),E(G)and F(G).A proper k-edge coloring of a graph G is an assignment π:E→ {1,2,...,k} such that for any adjacent edge e,e’,we have thatπ(e)≠π(e’).We say that G is k-edge colorable.The chromatic index,denoted by x’(G),of a graph G is the smallest positive integer k such that G is k-edge colorable.A strong edge coloring of a graph G is an assignment π:E→ {1,2,...,k} such that for any a pair of edges e and e’ which are at distance at most two satisfying π(e)≠π(e’).We say that G is strong edge k-colorable.The strong chromatic index,denoted by χ’s(G),of a graph G is the smallest positive integer k such that G is strong edge k-colorable.An(s,t)-relaxed strong edge k-coloring is a mapping π:E→ {1,2,...,k} such that for any edge e,there are at most s edges adjacent to e and t edges at distance two apart from e assigned the same color as e.The(s,t)-relaxed strong chromatic index,denoted byχ’(s,t)(G)is the minimum number of integer k such that G admits an(s,t)-relaxed strong k-edge coloring.For each edge e of G,we assign a list L(e)of possible colors to it,where L={L(e)e ∩ E}.If G has a proper edge coloring π such that π(e)∈ L(e)for each edge e,then we say that G is L-edge colorable or π is said to be an L-edge coloring of G.The graph G is k-edge choosable if it is L-edge colorable for every assignment L satisfying that |L(e)|≥ k for all edges e∈E.The list chromatic index of G,denoted by ch’(G),is defined to be the smallest positive integer k such that G is k-edge choosable.G is called strong edge L-colorable if for a given list assignment L={L(e)|e ∈ E},there exists a strong edge coloring π of G such that π(e)∈ L(e)for all e∈E.If G is strong edge L-colorable for any list assignment with |L(e)|≥ k for all e ∈E,then G is said to be strong edge k-choosable.The strong edge list chromatic index,denoted by ch’s(G),is defined to be the smallest integer k such that G is strong edge k-choosable.Further,G is called(s,t)-relaxed strong edge L-colorable if for a given list assignment L={L(e)|e∈ E},there exists an(s,t)-relaxed strong edge coloring π of G such that π(e)∈ L(e)for all e∈E.If G is(s,t)-relaxed strong edge L-colorable for any list assignment with |L(e)|≥ k for all e ∈E,then G is said to be(s,t)-relaxed strong edge k-choosable.The(s,t)-relaxed strong list chromatic index,denoted by ch’(s,t)(G),is defined to be the smallest integer k such that G is(s,t)-relaxed strong edge k-choosable.In 2017,He and Lin first proposed the concept of(s,t)-relaxed strong edge coloring.Recently,the research of(s,t)-relaxed strong edge coloring attracts much more attention around the world.We notice that the special case that s=t=0 corresponds to the concept of strong edge coloring.So(s,t)-relaxed strong edge coloring is a natural gener-alization of strong edge coloring.In this master thesis,we shall investigate this problem and give several results of(1,0)-relaxed strong list chromatic index for planar graphs with given girth.The framework is shown as follows:In Chapter 1,we shall introduce some basic concepts and then give a sketch of research status and results of this paper.In Chapter 2,3 and 4,we shall make use of contradiction and then study the struc-tural properties of each counterexample.The main methods are the coloring extension and the classical discharing argument.More precisely,we shall prove the following three results.(1)Every planar graph G with girth 6 satisfies that ch’(1,0)(G)≤ 3△(G)-1.(2)Every planar graph G with girth 7 satisfies that ch’(1,0)(G)≤ 3△(G)-2.(3)Every planar graph G with girth 9 satisfies that ch’(1,0)(G)≤ 3△(G)-3.