Acyclic Total Coloring And Acyclic Edge Coloring Of Graphs

The coloring of graphs is a very active research topic of graph theory.In recent years,due to the different rules and objects of coloring,the coloring theory of graphs is also increasingly rich.In this paper,we mainly study the question about the acyclic total coloring and the acyclic edge coloring of the graph.If φ is a proper total coloring of graph G,and it enables each cycle of graph G to contain at least 4 colors,then defines φ as the acyclic total coloring of graph G.The acyclic total chromatic number of the graph G,denoted by Xa"(G),is the minimum integerk makes the proper k-acyclic total coloring exist.The concept of acyclic total coloring of graphs was put forward by Sun and Wu,and gives the conjecture:for any graph G,Δ(G)+1≤xa"(G)≤Δ(G)+2.If φ is a proper edge coloring of graph G,and it enables graph G does not contain two-colored cycle,then defines φ as the acyclic edge coloring of graph G.The acyclic edge chromatic number of the graph G,denoted by Xa’(G),is the minimum integer k makes the proper k-acyclic edge coloring exist.In 2001,Alon et al.gave the conje-cture of the acyclic edge coloring:A(G)Ηr(G)≤Δ(G)+2 for any graph G.The conjecture about acyclic coloring provides an important reference for our research.This dissertation mainly gives acyclic total coloring of Pseudo-Halin graphs and K4-minor free graphs,and acyclic edge coloring of the triangle-free IC-planar graphs.In the first chapter,we mainly introduce the research background of graph theory,related concepts,and current research status of this paper.In the second chapter,acyclic total coloring of Pseudo-Halin graphs is studied by minimal counterexample.It is proved that if the graph G is Pseudo-Halin graph,then(?)w is an interior vertex which all neighbors are located at the boundary,and there is only one irregular neighbor.In the third chapter,for the acyclic total coloring of the K4-minor free graph,it is proved by a minimal counterexample:if the graph G is a K4-minor free graph,then(?)the structure(*)is two 3-cycles xx1zx and yy1zy,and d(z)= 4,d(x1)=d(y1)-2.In the fourth chapter,we study the acyclic edge coloring of the triangle-free IC-planar graphs.Using the discharging method and the minimal counterexample method,it is proved that if the graph G is a triangle-free IC-planar graph,xa’(G)≤Δ+7.In the fifth chapter,we mainly summarizing the relevant results of this dissertation,and make some prospects.