A Study On Several Kinds Of Edge Coloring For Graphs

With the introduction and development of the four-color problem,the coloring problem of graphs has become one of the important problems in graph theory.The coloring theory of graphs has also been widely used in computer science and bioinformatics.Strong edge coloring of graphs is an important coloring problem,and there have been many research results since it was proposed,especially the research on the conjecture of Erd?s and Ne?etril has greatly promoted the development of edge coloring,and also produced many new colorings.In 2015,Cardoso et al.proposed the concept of injective edge coloring,the concept of inclusion-free edge coloring was first proposed by Zhang.In this thesis,the injective edge coloring and inclusion-free edge coloring of graphs are discussed by using the relevant research tools of strong edge coloring of graphs.The thesis is divided into five sections.In section one,we introduce the related concepts of graphs and the main results of this paper.In section two,we discuss the injective edge coloring of generalized Petersen graph P(n,k)when k is 1 and 2.For P(n,1),when n is at least 6,if n is a multiple of 6,the injective edge chromatic number is 3,otherwise is 4;For P(n,2),when n is at least 8,the range of the injective edge chromatic number is from 4 to 5.In section three,we use discharging and Euler’s formula to study the injective edge coloring of the subcubic planar graphs,for a subcubic graph with girth of at least 8,the injective edge chromatic number is at most 6;for a subcubic graph with girth of at least 6,the injective edge chromatic number is at most 7.In section four,we discuss the bounds of the inclusion chromatic number of(2,Δ)bipartite graphs and(3,Δ)-bipartite graphs,and obtain that the upper bound of the inclusion chromatic number of(2,Δ)-bipartite graphs is 2Δ;the upper bound of the inclusion chromatic number of(3,Δ)-bipartite graph is 2Δ+1.In the last section we show by contradiction that the inclusion chromatic number of subcubic graphs is at most 7,and the equality holds if and only if the graph is isomorphic to K2,3(K2,3 is the graph obtained by dividing one edge of the complete bipartite graph K2,3 once).