Acyclic Total Coloring Of Graphs

Graph coloring was developed on the basis of the Four Color Problem.Coleman et al.calculated Hessian matrix by taking acyclic coloring as a model and using substitution method,which attracts more people to focus on acyclic coloring.All graphs considered are undirected,finite and nonempty.Let G =(V,E)be a graph,where V = V(G)and E = E(G)are the vertex set and the edge set of G,respectively.We use Δ(G),δ(G)to denote the maximum degree and the minimum degree of a graph G,respectively.The girth of a graph G,denoted by g(G),is the length of the shortest cycle in G.A graph which can be drawn in the plane in such a way that edges meet only at points corresponding to their common ends is called a planar graph.A proper total k-coloring of a graph G is a mapping from V(G)U E(G)to the color set[k]such that no two incident or adjacent elements x,y∈V(G)∪E(G)receive the same color.An acyclic total k-coloring is a proper total k-coloring of a graph G such that there are at least 4 colors on those vertices and edges incident with a cycle of G.The acyclic total chromatic number of G,denoted by Xα"(G),is the smallest number k of colors such that G has an acyclic total k-coloring.Our aim in this thesis is to investigate acyclic total coloring of some graphs e.g.some special classes of graphs,planar graphs with Δ≥8 and graphs with large girths.In chapter 1,we introduce some basic definitions and notions related to graph coloring.Next,we show the definitions of total coloring and acyclic total coloring.Finally,we provide the main results of this paper.In chapter 2,it is proved that acyclic total coloring conjecture holds for complete graphs and 2-degenerate graphs.In chapter 3,it is proved that acyclic total coloring conjecture holds for planar graphs with Δ≥8 by discharging method.In chapter 4,we study the acyclic total coloring of graphs with large girths,we prove that for any graph G which satisfies X"(G)≤△(G)+2,and for any integer r,1≤r≤2Δ(G),there exists a constant c>0 such that if g(G)≥cΔ(G)/rlog Δ2(G)/r then xa"(G)≤Δ(G)+r+2.In chapter 5,we summarize the main results of this thesis and give the prospects.