Acyclic Edge Coloring Of Graphs

Let G=(V, E) be a simple graph, where V and E denote the set of verticesand edges of G, and Δ and g(G) denote the maximum vertex degree and the girthof G, respectively. A graph G is called a planar graph if G can be embedded in theEuclidean plane such that any two edges intersect only at their ends. A plane graph isa particular drawing in the Euclidean plane of a certain planar graph.A proper edge k-coloring is a mapping c: E(G)â†'{1,2,..., k} such that any twoadjacent edges receive diferent colors. The chromatic index χ (G) of G is the smallestinteger k such that G is edge k-colorable. A proper edge k-coloring c of G is calledacyclic if there are no bichromatic cycles in G, i.e., the union of any two color classesinduces a subgraph of G that is a forest. The acyclic chromatic index of G, denotedby a (G), is the smallest integer k such that G is acyclically edge k-colorable.In1978, Fiam c′k introduced the concepts of acyclic edge coloring and acyclicchromatic index. By using a probabilistic method, Alon et al.(1991) frst gave alinear upper bound of acyclic edge coloring, that is for any graph G, a (G)≤64Δ.Later, Molloy and Reed (1998) improved this bound by showing that a (G)≤16Δ.For graphs with girth limited, Muthu et al.(2005) showed that a (G)≤4.52Δ if Gis a graph with g(G)≥220. The best general upper bound for a (G) in terms of Δis4Δ4obtained by Esperet and Parreau in2013. Fiam c′k (1978) and later Alonet al.(2001) posed the following famous Acyclic Edge Coloring Conjecture (AECC),independently.Conjecture (AECC): For any graph G, a (G)≤Δ+2.This conjecture remains open. Only some special graphs are known to satisfy theconjecture, such as cubic graph, non-4-regular graph with maximum degree at most4,2-degenerate graph, planar graphs with girth at least5, planar graphs without3-,4-cycles, or without4-,5-cycles.On the basis of previous work, we study the acyclic edge coloring of graphs in thisPh.D. Thesis. The thesis consists of fve chapters.In Chapter1, we collect some basic notations, give a chief survey in the relateddirections of acyclic edge coloring and state the main results obtained in the thesis.Meanwhile, we introduce some lemmas on characteristic properties of acyclic edgecoloring. In Chapter2, we study the acyclic edge coloring of4-regular graphs. It is provedthat if G is a4-regular graph, then a (G)≤6. This gives a solution to a problemby Basavaraju et al. in [Acyclic edge coloring of graphs with maximum degree4. J.Graph Theory,2009,61(3):192-209]. Combined with the known conclusions, AECCholds for any graph with maximum degree at most4.In Chapter3, we prove that a (G)≤Δ+7if G is a planar graph. This improvesthe result obtained by Basavaraju et al.[Acyclic edge-coloring of planar graphs. SIAMJ. Discrete Math.,2011,25(2):463-478], which says that every planar graph G satisfesa (G)≤Δ+12. Up to now, Δ+7is still the best upper bound for acyclic chromaticindices of planar graphs.In Chapter4, we study the acyclic edge coloring of planar graphs without shortcycles and obtain some sufcient conditions such that AECC holds. It is proved that ifG is a planar graph without i-cycles, i∈{3,4,5,6}, then a (G)≤Δ+2. Particularly,any planar graph G without i-cycles, i∈{4,5}, or without3-cycles adjacent to6-cyclesis acyclically edge (Δ+2)-colorable, i.e., AECC is true for these kinds of graphs. Tosome extent, this improves some known results on the acyclic edge coloring of planargraphs.In Chapter5, we study the acyclic edge coloring of outerplanar graphs and showthat any outplanar graph G with Δ≥5is acyclically edge Δ-colorable. Precisely, it isproved that alist(G)=Δ for any outerplanar graph G with Δ≥5, where alist(G) is theacyclic list chromatic index of a graph G. This result is best possible in the sense thatΔ cannot be reduced to3or4, since there are outerplanar graphs with Δ∈{3,4} thatare not acyclically edge Δ-choosable. Meanwhile, we give a sufcient condition for anouterplanar graph G with Δ=4to be acyclically edge4-colorable and show that thereexist infnitely many outerplanar graphs such that Δ=4and alist(G)=a (G)=5.