Edge Coloring And List Edge Coloring Of Graphs

Let G=(V,E)be a finite,simple and undirected graph with the vertex set V and the edge set E.A properκ-edge-coloring of G is a mapping from E into {1,2,...,κ} such that no adjacent edges receive the same color.If G has a properκ-edge-coloring,then G is said to be k-edge-colorable.The chromatic index,denoted byχ′(G),is the least integerκsuch that G isκ-edge-colorable.An edge-list-assignment L of G is a set of lists of colors which as-signs each edge e of G a list of colors L(e).If G has a proper edge-coloringφsuch thatφ(e∈L(e)for every e∈E,then G is said to be L-colorable.If G is L-colorable for every edge-list-assignment L with |L(e)|=κfor every e∈E,then we say that G is k-list-edge-colorable,orκ-edge-choosable.The edge choice number,or list-chromatic index of G, denoted byχ′_l(G),is the least integerκsuch that G isκ-edge-choosable.In 1964,Vizing provedthat every simple graph G has△(G)≤χ′(G)≤△(G)+1.A graph G is class 1 ifχ′(G)=△(G),and class 2 otherwise.In this thesis,we prove the following results:(1)If G is a planar graph with maximum degree 6 and without choral-5-cycles,then G is of class 1.(2)If G is a planar graph with maximum degree 5 and without inter-section triangles,then G is of class 1.(3)Let G be a graph with maximum degree 6 andχ(∑)≥0.G is of class 1 if one of the following conditions holds:(ⅰ)G contains no adjacent triangles; (ii)G contains no choral-5-cycles and choral-6-cycles.(4)If G is a planar graph with△(G)≠5 and without choral-5-cycles,then G is edge-(△(G)+1)-choosable.(5)Let G be a planar graph.G is edge-(△(G)+1)-choosable ifone of the following conditions holds:(a)G contains no choral-4-cycle and choral-5-cycle;(b)G contains no choral-5-cycle and choral-6-cycle.