Acyclic Edge Coloring Of Planar Graphs

Let Δ denote the maximum degree of a graph G. A proper k-edge edge coloring of G is an assignment of k colors to the edges of G such that no pair of incident edges share the same color. A proper k-edge coloring of a graph G is called acyclic if there is no bichromatic cycle in G. The acyclic chromatic number of G is defined as χ’a(G)=min{k|G admits an acyclic k-edge coloring}.The concept of acyclic edge coloring was first introduced by Fiamcik (1978). A conjecture posed first by Fiamcik (1978) and then again by Alon, Sudakov and Zaks (2001) states that, for every graph G, χ’a(G)≤Δ(G)+2. This is the famous Acyclic Edge Coloring Conjecture. Even for planar graphs, this conjecture remains open with large gap. So far, there are only a few graphs known to satisfy the conjecture.Following previous work, we study the acyclic edge coloring of some specific graphs by minimal principle and discharging method in this dissertation, and we obtain the following results:(1) For a planar graph G without intersecting triangles, Xa(G)≤Δ+4;(2) For a planar graph G without4-cycles, χ’a(G)≤Δ+3;(3) For a graph G with maximum average degree less than4, χ’a(G)≤Δ+2.