Study On Some Coloring Problems Of Graphs

Graph coloring originates from the Four-Color Conjecture and plays an indispen-sible role in the field of graph theory.It has wide applications in combination optimiza-tion,coding calculation,interactive network and so on.It is conceivable that acyclic coloring,acyclic list coloring and acyclic list edge coloring should be fully studied in this doctorial dissertation.An acyclic coloring(resp.acyclic edge coloring)of a graph G is a proper vertex(resp.edge)coloring such that there are no bichromatic cycles in G.The acyclic(resp.acyclic edge)chromatic number denote by a(G)(resp.a'(G)).An acyclic list coloring(resp.acyclic list edge coloring)of a graph G is a list coloring(resp.list edge coloring)such that there are no bichromatic cycles in G.The acyclic list(resp.acyclic edge list)chromatic number denote by al(G)(resp.al'(G)).Acyclic coloring comes from the problem of graph partition:the minimum number of subsets into which the vertex set of G is partitioned so that each subset induces an acyclic subgraph.In 1973,Grunbaum proposed the definition of acyclic coloring and gave the acyclic coloring conjecture that the acyclic chromatic number a(G)??+1 for every graph with maximum degree ?.In 2001,Alon et al.gave the acyclic edge coloring conjecture that the acyclic edge chromatic number a'(G)??+2 for every graph with maximum degree ?.Focus on both the conjectures,we mainly study the acyclic coloring,acyclic list coloring and acyclic list edge coloring of the graphs with small maximum degree.We take initiatives to expound our work by five aspects.In chapter 1,we show the research background,current research status,basic con-cepts of graph and the main results of this dissertation.In chapter 2,we consider the acyclic coloring of graphs and prove the following results:1.The acyclic chromatic number a(G)?9 for every graph G with maximum degree ??6,which improves the result a(G)?10 of Zhao et al.(2014);2.The acyclic chromatic number a(G)?12 for every graph G with maximum degree ??7,which improves the result a(G)?17 of Dieng et al.(2010);In chapter 3,we consider the acyclic list coloring of graphs and prove the follow-ing results:1.The acyclic list chromatic number al(G)?7 for every graph G with maximum degree ??5,which extends the result of Kostochka et al.(2011)to the acyclic list coloring;2.The acyclic list chromatic number al(G)?10 for every graph G with maxi-mum degree ??6,which extends the result of Zhao et al.(2014)to the acyclic list coloring;3.The acyclic list chromatic number al(G)?13 for every graph G with maxi-mum degree ??7,which extends the result of Dieng et al.(2010)to the acyclic list coloring and reduce the number of colors needed;4.We provide a short cut proof for the result that the acyclic list chromatic number al(G)?4(resp.al(G)<5)for every graph G with maximum degree ??3(resp.??4).In chapter 4,we consider the acyclic list edge coloring of graphs and prove the following results:1.The acyclic list edge chromatic number al'(G)?7 for every graph G with maximum degree ??4;2.The acyclic list edge chromatic number al'(G)?6 for every connected graph G with maximum degree ??4 and |E(G)|?2|V(G)|-1.According to the results above,both acylic edge coloring theorems of Basavaraju and Chandran(2009)are extended to the field of acylic list edge coloring.As far as topics are concerned,this dissertation is concluded in Chapter 5 and its evolution has not yet come to the end.New topics proposed on graphing theory might well be the major challenge and some potential work are prospected.