| The coloring of graphs has always been an important part of graph the-ory research and algorithm complexity analysis.Proper vertex coloring,edge coloring and total coloring are the major researches of classical graph coloring of which the“Four Color Theorem" and "Vizing" Theorem are important symbols.With the continuous development of the application background,some more complicated coloring ways have emerged.For example,total col-oring,list coloring,adjacent vertex distinguishing total coloring,neighbor sum distinguishing total coloring,etc.In particular,the study of strong edge-coloring has become the top concern.A κ-edge-coloring of a graph G is a function c:E(G)→[κ]such that the colors of every two adjacent edges are different.The chromatic index of G,denoted by χ’(G),is the minimum k for which G has a κ-edge-coloring.Vizing Theorem shows that χ’(G)≤△(G)+1,where △(G)is the maximum degree of G.A strong κ-edge-coloring of a graph G is an edge-coloring withκ colors in which every color class is an induced matching,i.e.the colors of every two edges that their distance is at most 2 are different.The strong chromatic index of G,denoted by χ’2(G),is the minimum k for which G has a strong κ-edge-coloring.In 1985,Erdos and Nesetril conjectured thatχ’s(G)≤5/4△(G)2.When G is a graph with maximum degree at most 3,the conjecture was verified independently by Andersen and Horak,Qing,and Trotter.In this paper,we consider the list version of strong edge-coloring.For each e ∈ E(G),let L(e)be the list of available colors of e,and let L = {L(e):e ∈ E(G)}.The graph G is strongly L-edge-colorable if there exists a strong edge coloring c of G such that c(e)∈ L(e)for every e ∈ E(G).For a positive integer k,a graph G is strongly κ-edge-choosable if G is strongly L-edge colorable for every L with |L(e)|≥k for all e ∈ E(G).The strong list-chromatic index,denoted by χ’s,l(G),is the minimum positive integer k for which G is strongly κ-edge-choosable.Note that χ’s(G)≤χ’s,l(G)for every graph G.At present,most of research on strong list edge coloring is regarding to the maximum degree and maximum average degree of the graph.In this paper,we will consider the list version of strong edge coloring.The article is divided into two chapters.The first chapter introduces the definitions and symbols of the coloring theory,and introduces the results of strong edge coloring,strong list edge coloring of the graph,and our main results.In the second chapter,we study the strong listedge coloring of subcubic graphs.By using the Combinatorial Nullstellensatz,Hall Theorem,the structural properties and coloring techniques of the graph,we show that every subcubic graph has strong list-chromatic index at most 11 and every planar subcubic graph has strong list-chromatic index at most 10. |
