Study On The Acyclic Edge Coloring Of Planar Graphs

The acyclic edge coloring of graphs is an important branch in coloring theory ofgraphs. And it is an important research object of graph theory too. It is significant onsolving problems like table problems, scheduling, circuit design, matter of time, signalprocessing and storage problem.An acyclic edge coloring of a graph G is a kind of normal edge coloring with nobichromatic cycles. The acyclic edge chromatic number of a graph G is the minimumnumber k which means there exists an acyclic edge coloring using k colors, and is de-noted by χa(G). In1978, F iamcik introduced the concept of acyclic edge coloring.In2001, Alon conjectured that χa(G)≤(G)+2is true for any graphs. This con-jecture has not been proved completely by now. Sun et al.(2008) proposed that theplanar graph with no3-cycles or mutual-intersected4-cycles has the following charac-ter: χa(G)≤(G)+3. W u et al.(2012) proved χa(G)≤(G)+4for the planargraph without5-cycles. Based on the research above, we did a further study on acyclicedge coloring and drew some conclusions in the following4chapters.Chapter One introduces the research background, research status and basic defini-tions.Chapter Two discuss the acyclic edge coloring of planar graphs without3-cyclesadjacent with5-cycles. First we get a structural lemma of this graph by using thedischarging method. Then we prove that χa(G)≤(G)+4for this graph by recoloringits minimal counterexample.Chapter Three prove that χa(G)≤(G)+3for planar graphs without3-cyclesintersected with3-cycles or4-cycles in the same way.Chapter Four give some considerable problems for further study.