Acyclic Edge-coloring Of Graphs

A proper edge-?-coloring of a graph G is a mapping c:E(G)? {1,2,…,?}such that any two adjacent edges e1 and e2 have c(el)? c(e2).The graph G is edge-k-colorable if it has an edge-?-coloring.The chromatic index of G,denotedx'(G),is the smallest integer k such that G is edge-?-colorable.A proper edge-?-coloring of G is called acyclic if there are no bichromatic cycles in G,i.e.,the union of any two color classes induce a subgraph of G that is a forest.The acyclic chromatic index of G,denoted a'(G),is the smallest integer k such that G is acyclically edge-?-colorable.The concept of acyclic edge coloring was first introduced by Fiamcik in 1978.Fiamcik(1978)and later Alon et al.(2001)put forward the following conjecture:For any graph G,a'(G)? ? + 2.In 1991,Alon et al.proved that a'(G)<64A for any graph G.This upper bound was gradually improved to that a'(G)? 16? by Molloy et al.(1998),that a'(G)? 4? by Esperet et al.(2013),and that a'(G)?[3.74(?—1)]+1 by Giotis et al.(2017).The above conjecture remains open.Basavaraju et al.(2012)proved that a'(G)? ? + 1 for any 2-degenerate graph G.In 2016,Wang et al.proved that a'(G)?? + 6 for any planar graph G.In this master thesis,we study the acyclic edge coloring of 4-regular graphs,3-degenerate graphs and chordal graphs.The thesis consists of four chapters.In Chapter 1,we collect some basic notations and give a chief survey in the related fields.And we state the main results obtained.In Chapter 2,we study the acyclic edge coloring of 4-regular graphs and prove that a'(G)? 6 for any 4-regular graph G.In Chapter 3,we study the acyclic edge coloring of 3-degenerate graphs and show that a'(G)? ? + 5 if G is a 3-degenerate graph.In Chapter 4,we study the acyclic edge coloring of chordal graphs and show the following two results:(1)If G is a chordal graph with 5 ? ? ? 6,then a'(G)? ? + 2;(2)If G is a 3-degenerate chordal graph with ? ? 13,then a'(G)? ? + 2.