Acyclic Edge Coloring Of Some Graphs

For a given graph G, let V(G), E(G) and Δ(G) denote the vertex-set, edge-set and maximum degree. A proper edge κ-coloring is a mapping c:E(G)â†'{1,2,...,κ} such that any two adjacent edges receive different colors. A proper edge κ-coloring of a graph G is called acyclic if there is no2-colored cycle in G. In other words, if the union of any two color classes induces a subgraph of G which is a forest. The acyclic edge chromatic number of G, denoted by a’(G), is the least number of colors in an acyclic edge coloring of G.In1973, the concept of acyclic vertex coloring was introduced by Grunbaum, and the concept of acyclic edge coloring was introduced by Fiamcik. In1991, Alon et al. proved that α’(G)≤64Δ(G) for any graph G. In1998, Molloy and Reed improved this bound and got α’(G)Δ16Δ(G). Fiamcik (1978) and later Alon, Sudakov and Zaks (2001) posed the following famous Acyclic Edge Coloring Conjecture:For any graph G, α’(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 some graphs. The thesis consists of four chapters.In Chapter One, we introduce some basic conceptions of graph theory, the primary results about the theory of acyclic edge coloring and the main results of the thesis.In Chapter Two, we study the acyclic edge coloring of2-outerplane graphs. It is proved that if G is a2-outerplane graph, then α’(G)≤Δ(G)+2, i.e., the above conjecture is true for this kind of graphs.In Chapter Three, we study the acyclic edge coloring of planar graphs without cycles of specific lengths. we prove that the acyclic edge chromatic number of a planar graph G is at most (Δ(G)+1) if G contains no i-cycles,4≤i≤8, or any two3-cycles are not incident with a common vertex and G contains no i-cycles, i=4and5.In Chapter Four, we study the acyclic edge coloring of the square cycle, we prove that the acyclic edge chromatic number of C62is6and the acyclic edge chromatic num-ber of Cn2is5when n is not equal to6.