Graph Coloring,Labeling And Rainbow Matchings In Hypergraphs

Graph coloring,labeling and extremal graph theory are important re-search topics in graph theory.They have important applications in Combina-torial Optimization,Computer Science,Pattern Matching,and so on.Thus,they have attracted much attention all the time.The aim of this thesis is to discuss the following coloring problems,labeling problems and rainbow Turan problems for matchings in hypergraphs.In this thesis,unless otherwise specified,all the graphs we considered are undirected,finite,simple and nonempty.Given a graph G,we use V(G),E(G),?(G),?(G),mad(G)(or simply,V,E,?,?,mad)to denote the vertex set,the edge set,the maximum degree,the minimum degree and the maximum average degree of graph G,respectively.Fristly,we discuss the neighbor product distinguishing total coloring of graph G.Given a graph G =(V,E),a proper[k]-total coloring c of G is a proper total coloring c of G using colors of the set[k]= {1,2,…,k}.Let p(v)denote the product of the color on a vertex v and colors on all the edges incident with v,that is,p(v)= C(v)?uv?E(G)Cc(uv)For each edge uv E(G),if p(u))?p(v))then we say the coloring c distinguishes djacent vertices by product and call it a neighbor product distinguishing k-total coloring of G.By X"?(G),we denote the smallest value of k in such a coloring of G.We conjectured that ?(G)+ 3 colors enable the existence of a neighbor product distinguishing total coloring for any graph with at least two vertices.In Chapter 2,we obtain that for planar graph G with?(G)>10,X"?(G)? max{?(G)+2,13}.In addition,for graph G with mad(G)<3,X"?(G)?max{?(G)+2,7}.Graph labeling is a special kind of graph coloring.In this thesis,we mainly discuss antimagic labeling of graphs.An antimagic labeling of a graph G is a bijection from the edge set E(G)of G to the set ?1,...,IE(G)|?such that no two vertices in G have the same vertex-sum,where the vertex-sum of a vertex?E V(G)is the sum of labels of all edges incident to.We say that G is antimagic if G admits such an antimagic labeling.In the year 1990,Haatsfseld and Ringel raised such a conjecture:Every connected graph other than K2 is antimagic.This conjecture has been proved for regularg graphs,dense graphs and some special graphs.However,even for trees,this conjecture is still open.Motivated by this conjecture,in the year 2010,Hefetz,Miitze,and Schwartz initiated the study of antimagic abelings of digraphs.A labeling of a digraph D with m arcs is a bijection from the set of arcs of D to {1,...,m.} A labeling of D is antimagic if no two vertices in D have the same vertex-sum,where the vertex-sum of a vertex u? V(D)for a labeling is the sum of labels of all arcs entering u minus the sum of labels of all arcs leaving u.They conjectured that every connected graph admits an antimagic orientation,where an orientation D of a graph G is antimagic if D has an antimagic labeling.This conjecture has been proved to hold for odd regular graphs,biregular bipartite graphs,dense graphs and some special graphs.It remained unknown whether every disjoint union of cycles admits an antimagic orientation.In Chapter 3,we first answer this question in the positive by proving that every 2-regular graph has an antimagic orientation.We then show that for any integer d>2,every connected,2d-regular graph has an antimagic orientation.Given a k-uniform hypergraph H on n vertices,if H does not have a matching of size s?1,then how many edges can exist in H?Such a problem was raised by Erdos in the year 1965,which is regarded as a very important problem in the field in extremal combinatorics.Generally,we use exk(n,s)to denote the maximum number of edges of a k-uniform hypergraph on n vertices without s + 1 disjoint edges.Erdos conjectured that this problem has only two extremal constructions.The first one is a clique consisting of all the k-subsets on k(s+ 1)-1 vertices,which obviously has matching.number s.The second example is a k-uniform hypergraph on n vertices containing all the edges intersecting a fixed set of s vertices,which also forces the matching number to be at most s.That is,exk(n,s)= max{(k(s+1)-1 k),(n k)-(n-s k)}.Now,if H is properly colored and does not have a rainbow matching of size s+ 1,then how many edges can exist in H?Obviously,such a problem is a generalization of the above problem raised by Erdos.We use ex*k(n,s)to denote the maximum number of edges of a properly colored k-uniform hypergraph on n vertices without a rainbow matching of size s + 1.We conjecture that ex*k(n,s)= max(k(s+1)-1 k),(n k)-(n-s k)}.In Chapter 4,we prove that if n ? 7.6s,this conjecture holds for every 3-uniform hypergraph.More generally,suppose that H = {H1,H2,…,Hs+1};is a family of k-uniform hypergraphs on the same vertex set,if we can take each edge from each Hi to consist a rainbow matching of size s+1,then how many edges can exist in each Hi?Aharoni and Howard considered such a problem and conjectured that max(k(s+1)-1 K),(N K)-(N-S K)+1 1 is enough.We consider a family H consisted of S + 1 properly colored k-uniform hypergraphs and conjecture that if each hypergraph has at least max((k(s+1)-1k),(nk)-(n-s k}+1 edges,then we can find a rainbow matching of size s+ 1 in H.Here,a matching is rainbow means that not only each edge is taken from each Hi and all edges are pairwise vertex disjoint,but also the colors of edges are pairwise disjoint.In Chapter 4,we prove the conjecture holds if n ?3k2s.