Acyclic Edge Coloring Of Planar Graphs With Large Maximum Degree

Graphs are very powerful tools for creating mathematical models of a wide variety of situations. The study of graph started over two hundreds years ago. Graph coloring theory has a central position in graph theory. It has interesting real-life applications in optimization, computer science, network design, computation of Hessians matrix and so on. The aim of this thesis is to discuss the acyclic edge colorings of planar graphs with large maximum degree.Let G be a graph with vertex set V(G) and edge set E(G). A proper k-edge-coloring of G is a mapping φ:E(G)â†'{1,2,A,k} such that no pair of adjacent edges are colored with the same color. A proper k-edge-coloring is called acyclic if there is no2-colored cycle in G. The least number of colors in an acyclic edge coloring of G is called acyclic chromatic number of G, denoted by χα (G).Acyclic coloring problems are specialized coloring problems that arise in the efficient computation of Hessians matrix using automatic differentiation or finite differencing, when both sparsity and symmetry are exploited. In2001, Alon, sudakov and Zaks gave the following conjecture:â–³(G)≤χα(G)≤△(G)+2for all graphs G.In this thesis, we give some bounds on acyclic edge chromatic number of planar graphs with large maximum degree. We have constrcucted our work in three chapters.We begin Chapter1with basic concepts and definitions. Then we describe the histroy and the development of this problem. Finally, we outline the main results of this thesis.In Chapter2, we considered the acyclic edge colorings of planar graphs without intersecting triangles by combining method and partial coloring extension technique. We get two upper bounds. In Section2.1we proved that if G contains neither4-cycles nor intersecting triangles, then χα(G)≤△(G)+3. In Section2.2, we prove that if G does not contain any intersecting triangles andâ–³(G)≥12, then χα(G)≤△(G)+4.In Chapter3, we discuss the acyclic edge colorings of planar graphs without adjacent triangles. In Section3.1, we show that if planar graphs G withâ–³(G)≥18does not contain any adjacent triangles, then χα(G)≤△(G)+5. In Section3.2, we present some unsolved problems.