The Coloring Problems Of Graphs By Using The Probability Methods

Probability theory and mathematical statistics have played a key role in big data problems in recent years.It studies the quantitative relationship between random phenomena.Moreover,probability theory and mathematical statistics are widely used in finance,economy,biology and other fields.In this paper,we use probability methods such as Lovász local lemma,Markov inequality,and other methods to solve some coloring problems in graph theory.Graph coloring has always been a hot topic in graph theory,which has been widely used in statistical analysis,computer science,communication engineering and other practical problems.This paper studies several kinds of coloring problems in graph coloring theory.The Adjacent Vertex Strongly Distinguishing Total Coloring in graph G is a mapping f:V(G)?E(G)?{1,2,…,k},where k is a natural number,(1)for(?)uv?E(G),f(u)?f(v),f(u)?f(uv)?f(v);(2)for any two adjacent edges uv and uw in graph G,where v?w,f(uv)?f(uw);(3)for (?)uv?E(G),the color set of its endpoints satisfies Cf(u)?Cf(v),where the color set of vertex u is Cf(u)={f(u)}?{f(v)|uv?E(G)}?{f(uv)|uv?E(G)}.The minimum k value satisfying this coloring is the adjacent vertices strongly distinguishable total chromatic number of a graph G,which is denoted as ?ast(G).Vertex Distinguishing Total Coloring is also a mapping ?,on the basis of satisfying(1)and(2),and the color set of vertex u in graph G is defined as C?(u)={?(u)}?{?(uv)|uv?E(G)}.The minimum k value that satisfies this coloring is the vertex distinguishable total chromatic number of a graph G,which is denoted as ?vt(G).Vertex Distinguishing Edge Coloring is also a mapping ?:V(G)?E(G)?{1,2,…,k},such that any uv,uw?E(G)(v?w)satisfy ?(uv)??(uw);u,v?V(G)(u?v),C?(u)?C?(v),where C?(u)={?(uv)|v?V(G),uv?E(G)}.The minimum k value satisfying this coloring is the vertex distinguishable edge chromatic number of a graph G,which is denoted as ?'vd(G).In this paper,besides studying the coloring of general graphs,we also study the coloring of planar graphs and improve their chromatic numbers.The 2-distance coloring of G is a mapping of ?:V(G)?{1,2,…,k},such that for any two vertices u and vertices v in graph G whose distance is less than 2,there is?(u)??(v).The minimum k value satisfying the above coloring is called the 2-distance coloring number of the planar graph and is denoted as ?2(G).L(v)is the set of available colors for all vertices in graph G.If ? is a 2-distance coloring for the graph G and there is ?(v)?L(V)for any v?V(G)in the graph G,then ? is a L-2-distance coloring for graph G.The minimum k value satisfying the above coloring is called the 2-distance list coloring number of the planar graph,denoted as ?2l(G).In this paper,we study the application of probabilistic methods in several kinds of graph coloring problems.It mainly related to Adjacent Vertex Strongly Distinguishing Total Coloring,Vertex Distinguishing Total Coloring,Vertex Distinguishing Edge Coloring,and list 2-distance coloring of planar graph with large girth and without some short cycles.In the first chapter,some basic concepts of probability theory and mathematical statistics are introduced in the first section.In the second section,some basic concepts in the field of graph theory dyeing are given,and the previous research results are summarized.Finally,in the third section,some results of this paper are given.In the second chapter,some problems can be solved well by applying probability to dyeing problems.In the first section,Lovász local lemma in probability theory and mathematical statistics is introduced.In the second section,this lemma is applied to improve the upper bound of chromatic number of strongly distinguishable total coloring at adjacent points,and this result is the best.In the third chapter,because it is difficult to study Vertex-Distinguishing-Edge Coloring and Vertex Distinguishing Total Coloring,the Markov inequality and the first distance principle play an important role in probability theory and mathematical statistics.We try to use these two theorems and further analyze them on the basis of previous work,and improve their chromatic number upper bound.In the fourth chapter,we study the list 2-distance coloring of planar graph,and prove it by weight transfer and contradiction method to prove two results:(1)If the graph G is a planar graph of ??40 and g?5,then ?2l(G)??(G)+4;(2)If G is a planar graph without 3-,5-cycles and intersecting 4-cycles.then ?2l(G)??(G)+4.In the fifth chapter,we summarize the research results of this paper and gives the further research problems.