List Edge Coloring And Linear Coloring Of Planar Graphs

A graph G is a pair G= (V,E), which contains a finite nonempty set V of objects called vertices and a set E of 2-element subsets of V called edges. The set V and E are the vertex set and edge set of G. A graph does not consist parallel edges and loop that is called simple graph.A k-edge coloring of a graph G is a mappingφ:E(G)â†'{1,2,…, k},and k is an integer. An edge-coloring is called proper if adjacent edges receive different colors. The edge chromatic number of G, denoted byχ′(G), is the smallest integer k such that G has a proper edge-coloring. We say that L is an edge assignment for the graph G if it assigns a list L(e) of possible colors to each e∈E(G). If G has a proper edge-coloringφsuch thatφ(e)∈L(e) for every egde e∈E(G), then we say that G is egde-L-colorable orφis an egde-L-colorable of G. The graph G is edge-k-choosable if it is edge-L-colorable for every edge assignment L satisfying|L(e)|≥k for each edge e∈E(G). The list edge chromatic number of G, denoted byχl′(G), is the smallest integer k such that G has a proper edge-k-choosable. The list chromatic numberχl(G) and the list total chromatic numberχl″(G) of G can be defined similarly in terms of coloring only vertices and both vertices and edges. It follows directly from the definition thatχl′(G)≥χ′(G)≥Δ(G) andχl″(G)≥χ″(G)≥Δ(G)+1.A proper vertex coloring of a graph is called linear if the subgraph induced by the union of any two color classes is a linear forest, i.e. a set of vertex-disjoint paths. Let lc(G) be the minimum number of colors in a linear coloring of the graph G. We call lc(G)the linear chromatic number of G.In this article,we mainly study edge list coloring and linear coloring.We improve and complement some known results by previous researchers.In chapter 1,we show some basic notions used in this article and give the back-ground of interrelated field and investigative present situations. Main results in this article are stated.In chapter 2,we main prove results about edge list coloring:the list chromatic indexχl′(G)=Δand the list total chromatic numberχl″(G)=Δ+1 ifâ–³(G)=6 and G has no 4一cycles and 7-cyclesï¼›the list chromatic indexχl′(G)=Δand the list total chromatic numberχl″(G)=Δ+1 ifΔ(G)=5 and G has no 4,6,8-cycles.In chapter 3,we main prove that if G is a planar graph and satisfy one of following conditions,then lc(G)=[Δ(G)/2]+1.(1)Δ(G)≥5且g(G)≥9.(2)Δ(G)≥11且g(G)≥7.