Some Graph Coloring Problems And Rainbow Matchings In Hypergraphs

Graph coloring theory and Extremal graph theory are two important research topics in Graph theory.They have been widely applied in Computer Science,Information Security and Pattern Matching and so on.In this thesis,we mainly consider the following coloring problems and Turan problems for rainbow matchings in 3-uniform hypergraphs.Given a graph G =(V,E)and a proper total coloring ?:V?E?{1,2,...,k} of G.Let m?(v)be the sum of colors of v and edges incident with vertex v,i.e.,m?(v)= ?(v)+?uv?E?(uv).We call m?(v)the induced color sum of vertex v under coloring ?.If m?(u)? m?(v)holds for any edge uv ? E,then the proper total coloring ? of G is said to be a neigh-bor sum distinguishing total coloring of G.The smallest integer k such that graph G has a neighbor sum distinguishing total coloring is the neighbor sum distinguishing total chromatic number,denoted by ?"?(G).As for the neighbor sum distinguishing total chromatic number,Pilsniak et al.conjec-tured that ??(G)?(G)+3 holds for any connected graph G on at least two vertices.In Chapter 2,we study the list neighbor sum distinguishing total coloring which is defined as follows.Let L={Lx| x ? V ? E} be a family of lists.If there exists a neighbor sum distinguishing total coloring?:V ? E ? ?x?V?ELx such that ?(x)?Lx holds for any x?V?E,then we call 0 a neighbor sum distinguishing total coloring under L.If for any L = ?Lx | x? V? E} with |Lx|?k for all x?V ? E,there always exists a neighbor sum distinguishing total coloring under L of G,then we say G is k-neighbor sum distinguishing total choosable.The minimum number k such that G is k-neighbor sum distinguishing total choosable is the neighbor sum distinguishing total choice number of G,denoted by ch"?(G).Let col(G)be the smallest number k for which there exists an enumeration of the vertices of G such that for any vertex v,fewer than k of its neighbors proceeds it.Combining the Combinatorial Nullstellensatz and some structural properties of graphs,we prove that ch"?(G)<?(G)+2col(G)-2 for any graph G and ch"?(G)? ?(G)+ 2col(G)-3 if graph G is not a forest and ?(G)? 4.In ad-dition,for any graph G of maximum degree 3,we also show that ch"?(G)?7 holds and if mad(G)<20/7,then ch"?,(G)<6 holdsSuppose ?:E??1,2,...,k} is a proper edge coloring of graph G.Define C?(v)to be the set of colors of edges incident with vertex v,i.e.,C?(v)= {?(uv)| uv ? E}.We say that C?(v)is the induced color set of vertex v under coloring ?.If C?(u)?C?(v)holds for any edge uv? E,then the proper edge coloring ? of G is said to be a neighbor set distinguishing edge coloring of G.The smallest integer k such that graph G has a neighbor set distinguishing edge coloring is the neighbor set distinguishing edge chromatic number of G,denoted by ?'a(G).In 2002,Zhang et al.proposed this notation and conjectured that ?'a(G)??(G)+ 2 holds for any connected graph G on at least six vertices.A graph is said to be a normal graph if this graph contains no isolated edge.In Chapter 3,we study the list neighbor set distinguishing edge coloring of planar graphs and prove that for any normal planar graph G,it holds that ?+ 3,??22;ch'a(G)?? + 4,18 ???21;22,? ? 17,where ch'a(G)is the neighbor set distinguishing edge choice number of G.We define the induced color sum of a vertex v under a proper edge coloring ? to be ?uv?E?(uv).Similar to the definition of neighbor sum distinguishing total coloring,we can define the neighbor sum distinguishing edge coloring and the neighbor sum distinguishing edge chromatic number?'?(G)of a graph G.As for the neighbor sum distinguishing edge chromatic number,Flandrin et al.conjectured that ?'?(G)??(G)+ 2 holds for any connected normal graph G if G is not a 5-cycle.No? that a neighbor sum distinguishing edge coloring of a graph G must be a neighbor set distinguish-ing edge coloring of graph G.Hence,this conjecture is also a generalization of the conjecture concerning neighbor set distinguishing edge coloring.In Chapter 3,we study the list neighbor sum distinguishing edge coloring of planar graphs and prove that for any normal planar graph G,it holds that? + 6,?? 22;ch'?(G)?? + 7,17 ??? 21;24,?? 16,where ch'?(G)is the neighbor sum distinguishing edge choice number of G.A proper edge coloring 0 of a graph G is said to be an r-acyclic edge coloring of G,if any cycle C of graph G contains at least min{|C|,r} colors.We call the smallest number of colors such that there is an r-acyclic edge coloring of graph G the r-acyclic edge chromatic number of G,denoted by A'r(G).In 2005,Greenhill et al.proved that for any integer r>4,it holds that A'r(d)= ?(d?r/2?),where A'r(d):= max{A'r(G)| ?(G)= d}.The upperbound of A'r(d)they gave is?25r+4/6 r(r + 2)]??r/2?.In Chapter 4,we study r-acyclic edge colorings and prove the following results via entropy compression method.If r>4 is odd,then it holds that A'r(G)<2??r/2?+O(?r+1/3)for any graph G;If r? 4 is even,then it holds that A'r(G)???r/2+ O(?r+1/3)for any graph G,which is asymptotically optimal.In addition,if the girth of graph G is at least 2r-1,then A'r(G)?(9r-7)? + 10r-12.These results are big improvements of the previous ones.Suppose that H= {H1,H2,...,Ht+1} is a family of k-uniform hyper-graphs on the same vertex set.We call M a rainbow matching of H if M is a matching containing at most one edge from each Hi(i E[t + 1]).Let exk(n,t)be the maximum number of edges of a k-uniform hypergraph on n vertices without t + 1 disjoint edges.Determining the value of exk(n,t)is a very important Turan problem.In 1965,Erdos conjectured that eXk(n,t)=max {(k(t+k)-1/k,(nk)-(n-k k)}.Recently,Aharoni and Howard considered a rainbow version of this problem and conjectured that if each Hi(i ?[t+1])is a k-uniform hypergraph with n vertices and at least exk(n,t)+ 1 edges,then H contains a rainbow matching of size t + 1.In Chapter 5,we consider this conjecture for 3-uniform hypergraphs and prove that this conjecture holds when n ?3.9t + 10.