Spanning Structures In Randomly Perturbed Hypergraphs And Graph Coloring Problems

The theory of random graphs originated from a series of papers pub-lished by Erdos and Renyi in the period 1959-1968.The theory is located at the intersection of graph theory,combinatorics and probability theory.Through several decades of development,it has become an independent and fast-growing branch of discrete mathematics,with applications to theoretical computer science,natural science,social science and to discrete mathematics itselfRandomly perturbed(hyper)graph is a new type of graph model in-troduced by Bohman Frieze and Martin,which asked how many random(hyper)edges required to add to a dense(hyper)graph in order to make the resulting(hyper)graph satisfy some structural property with high probabili-ty.In recent years,the model has been studied extensively.In Chapter 2 and Chapter 3,we study the appearance of some spanning structures in random-ly perturbed hypergraphs,which include power of a tight Hamilton cycle,perfect matching and factor.We obtain the following results by applying the "absorption method" pioneered by Rodl,Rucinski and Szemeredi,which has been a powerful tool in finding spanning subgraphs,and combining some results from the binomial random hypergraphsFor the existence of power of a Hamilton cycle,we show that for k>3,r>2 and α>0,there exists ε>0 such that if p=p(n)≥ n-(?)-1-ε and H is a k-uniform hypergraph on n vertices with minimum codegree at least on,then asymptotically almost surely the union H∪H(k)(n,p)contains the rth power of a tight Hamilton cycle.The bound on p is optimal up to the value of ε and this answers a question of Bedenknecht,Han,Kohayakawa and Mota.For the existence of perfect matching,Krivelevich,Kwan and Sudakov[Combin.Probab.Comput.25(2016),909-927]proved that adding linearly many random edges to a k-graph with linear minimum codegree ensures the emergence of a perfect matching with high probability,and suggested investigating the effect of using weaker density assumptions on the host k-graph in lieu of a minimum codegree condition.Note that a perfect matching is an F-factor,where F is a single edge.Following their proposal,we study the appearance of F-factors in randomly perturbed hypergraphs for arbitrary F,using the weakest possible notion of density,namely vertex degree.We determine the optimal number of random edges that need to be added to a k-graph H with minimum vertex degree Ω(nk-1)to ensure an F-factor with high probability,where F belongs to a certain class of k-graphs F,which includes,e.g.,all k-partite k-graphs,(?)and the Fano plane.In particular,taking F to be a single edge,this settles the conjecture proposed by Krivelevich,Kwan and Sudakov about the existence of perfect matching in randomly perturbed hypergraphs.We also address the case when the host graph H is not dense,indicating that starting from certain such H is essentially the same as starting from an empty graph(namely,the purely random model).Another classical and important research topic in graph theory is graph coloring theory.On the one hand,there are many beautiful theorems and ancient and beautiful conjectures,such as Four-Color Theorem.On the other hand,it has many real-life applications in storage problem,timetabling problem,production scheduling and electrical networks etc.At the end of this paper,we mainly study the(list)adjacent vertex distinguishing total coloring of planar graphs,A(proper)k-total coloring Φ:V(G)U E(G)→{1,2,…,k} is called adjacent vertex distinguishing if CΦ(u)≠CΦ(v)for each edge uv∈ E(G),where CΦ(u)is the set of the color of u and the colors of all edges incident with u.We use χ"a(G)to denote the smallest value k in such a coloring of G.Zhang et al.[Sci.China Ser.A.48(2005),289-299]first introduced this coloring and conjectured that χ"a(G)≤ Δ(G)+3 for every simple graph G.It is known that X"a(G)≤Δ(G)+3 for every planar graph with Δ((G)>9.In this paper,we succeed in proving the conjecture for every planar graph withΔ(G)>8 by using Alon’s Combinatorial Nullstellensatz and discharging method.Furthermore,for the list version of this coloring,it is known that,ch"a(G)≤Δ(G)+3 for every planar graph with Δ(G)≥11,where ch"a(G)is the adjacent vertex distinguishing total choosability.In this paper,we show that if G is a planar graph with Δ(G)≥ 10,then ch"a(G)≤ Δ(G)+3.