Acyclic Edge Coloring Of Plane Graphs

Let G be a graph with edge set E(G), maximum degreeΔ(G) and girth g(G). A proper edge k-coloring is a mapping c:E(G)â†'{1,2,...,k} such that any two adjacent edges receive different colors. A proper edge k-coloring c of G is called acyclic if there are no bichromatic cycles in G. The acyclic chromatic index of G, denoted by a'(G), is the smallest integer k such that G is acyclically edge k-colorable.The concept of acyclic edge coloring was introduced by Fiamcik in 1978. Alon et al. (1991) proved that a'(G)≤64Δ(G) for any graph G by using a probabilistic method. Later, Molloy and Reed (1998) improved this bound and got a'(G)≤16Δ(G). In 2005, Muthu, Narayanan and Subramanian showed that a'(G)≤4.52Δ(G) if G is a graph with g(G)≥220. In 2001, Alon, Sudakov and Zaks posed the following famous Acyclic Edge Coloring Conjecture.Conjecture:For any graph G, a'(G)≤Δ(G)+2.This conjecture remains open. Only some special graphs are known to satisfy the conjecture. In this master thesis, we study the acyclic edge coloring of planar graphs. The thesis consists of four chapters.In Chapter 1, we collect some basic notations, give a chief survey in this direction and state the main results obtained.In Chapter 2, we study the acyclic edge coloring of planar graphs with girth at least 5. It is proved that if G is a planar graph with g(G)≥5, and if there is a pair (k,m)∈{(3,11), (4,8), (5,7), (8,6), (12,5)} such thatΔ(G)≥k and g(G)≥m, then a'(G)=Δ(G). This improves some known results on the acyclic edge coloring of planar graphs.In Chapter 3, we prove that if G is a planar graph with girth 4, then a'(G)≤Δ(G)+2, i.e., the above conjecture is true for this kind of graphs.In Chapter 4, we provide a complete characterization for a K4-minor free graph G withΔ(G)≠4 under the condition of a'(G)=Δ(G) or a'(G)=Δ(G)+1. This extends the result for the acyclic chromatic number of outerplanar graphs.