List Strong Edge-Coloring Of Graphs

This article describes the result associated with the list strong edge-coloring problem for graphs with maximum degree of 4.Let G be a graph,V(G)and E(G)represent its vertex set and edge set,respectively.Let v ∈V(G),then the degree of vertex v uinnG is denoted by dG(v),the maximum and minimum degree of G are denoted by △(G)andδ(G)respectively.The edge-coloring problem of a graph is to color all edges of the graph and requires that any two adjacent edges have different colors.The strong edge-coloring of the graph is based on the edge-coloring,but it further requires that all three edges on a path of length 3 must be colored differently,and we denote the strong chromatic index by χs’(G)which is the minimum number of colors that allows a strong edge-coloring of G.Erdos and Nesetril conjectured in 1985 that:If G is a graph with maximum degree △(G),thenThe conjecture is proved right when △ ≤ 3.For △= 4,while the conjec-ture says that χs’(G)≤ 20,the best known upper bound is 22 due to Cranston[5]in 2006,which was improved to 21 by Huang,Santana and Yu recently.In this paper we extend the result of Cranston[5]to list strong edge-coloring,that is to say,we prove that when △= 4 the upper bound of list strong chromatic index is 22.As for △>4,the results of strong edge-coloring are not too much yet.List strong edge-coloring is the generalization of strong edge-coloring,which is a strong edge-coloring such that each edge e receives a color in a prescribed color list L(e).In this paper we extend the result of Cranston[5]to list strong edge-coloring,that is to say,we prove that when △= 4 the upper bound of list strong chromatic index is 22.This paper is divided into four chapters:In Chapter 1,we will first introduce some basic concepts of graph theory,the specific definitions of strong and list strong edge-coloring and briefly de-scribe the background and development of these two problems,then we will introduce the main results of the above conjecture,strong edge-coloring of planar graphs and k-generate graphs,list strong edge-coloring problems re-spectively.Finally,we will give the main result of this paper,the issues that can be further discussed and the structure of the whole article.In Chapter 2,we will give special definitions of this paper,useful theorem-s and important lemmas,the concepts of distance and distance set will also be introduced,the Combinatorial Nullstellensatz,Hall’s theorem,inclusive-exclusive principle are given,and we will prove two very useful lemmas.In chapter 3,based on the idea of reduction to absurdity,a minimal coun-terexample to the main theorem is set,and several structural properties of this minimal counterexample are further demonstrated,including its regulari-ty,whether it is a simple graph and the structure of the circles in it,which all will simplify the proof of the last chapter.In chapter 4,we prove the main result of this paper.According to the structural properties of the minimal counterexample in Chapter 3 and the method of approximating the local structure,we will finish the list strong edge-coloring of this counterexample of the main theorem,which proves the correctness of the main result.